中国科学技术信息研究所--国家工程技术数字图书馆

[学位论文] 罗润梓上海大学 2005年博士导师: 孙世杰共105页

摘要 : 本文主要考虑平行机半在线排序问题.本文首先简要介绍了排序问题、竞争比分析和近似算法等基本概念，总结了近年来出现的各个半在线模型及其有关结果. 第二章考虑已知工件最大加工时间的半在线模型，目标为极大化最小机器负载.主要讨论两个问题：... 展开本文主要考虑平行机半在线排序问题.本文首先简要介绍了排序问题、竞争比分析和近似算法等基本概念，总结了近年来出现的各个半在线模型及其有关结果. 第二章考虑已知工件最大加工时间的半在线模型，目标为极大化最小机器负载.主要讨论两个问题：1三台同类机的情形，我们给出min3算法并且证明此算法的竞争比为max{r+1，3s+r+11+r+s}.min3算法是紧的且当1≤s≤2、r=1时是最优的.2m台特殊同类机问题，我们给出Cmin算法及其竞争比max{m-1，ms+m-1}，并证明Cmin算法是紧的且当1≤s≤(m-1)(m-2)(m≥3)时是最优的. 第三章考虑已知工件最大加工时间的半在线问题，目标为极小化机器最大负载.主要讨论四个问题：1对于两台同类机的问题，我们给出竞争比分别为2(s+1)s+2(1≤s≤2)和s+1(s＞2)的Qmax2算法，并且证明此算法是紧的且相应某些s的特殊值是最优的.2对于三台同类机半在线问题，我们给出Qmax3算法并证明此算法的竞争比不大于2(r+s+1)2r+s(1＜s≤2)和r+2s+1(s＞2)且严格小于2.3对于三台特殊同类机问题，给出Qmax3t算法并证明其竞争比不大于s+2(1≤s≤2)和s+2s(s＞2)且恒小于2.4最后我们考虑m台同型机问题，给出一个竞争比为2m-3的Cmax算法并证明此算法对任何m≥3是紧的. 第四章中，我们考虑已知工件总加工时间的两台同类机半在线问题，目标为极大化最小机器负载.我们给出Q2min算法并证明此算法的竞争比小于2+√22，而此问题竞争比的下界为1+√52.同时证明当s=1+√52时Q2min算法最优的. 在第五章中，我们考虑带机器准备时间的已知工件总加工时间的半在线问题.第一节考虑P2，ri｜sum｜Cmin问题，给出Prsum算法并证明此算法的竞争比为32且是最优算法.在第二节则考虑Q2，ri｜sum｜Cmax问题，给出Qrmax算法并证明此算法的竞争比为√2；同时给出此问题的一个下界. 第六章我们首先引进一个新的半在线术语：半在线模型的松弛，然后我们介绍一个新的半在线模型：已知工件最大加工时间在某一区域内，即knownlargestjobinterval模型.第一节考虑P2｜knownlargestjobinterval｜Cmax问题，我们给出Pinterval算法及其竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过433.第二节考虑P2｜knownlargestjobinterval｜Cmin问题，我们给出Pinterval算法的竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过14. 收起

关键词 : 排序问题半在线竞争比平行机

2. 工件加工时间非恒定的排序模型研究

[学位论文] 程明宝上海大学 2006年博士导师: 孙世杰共102页

摘要 : 排序问题是运筹学中一类重要的组合优化问题.在经典排序问题中，通常假设工件的加工时间是恒定的.但是在诸多有实际背景的问题中，工件的实际加工时间由于加工机器设备，工件本身以及加工顺序(位置)等因素的影响而不可能始终是恒定的.此产生一类重要的... 展开排序问题是运筹学中一类重要的组合优化问题.在经典排序问题中，通常假设工件的加工时间是恒定的.但是在诸多有实际背景的问题中，工件的实际加工时间由于加工机器设备，工件本身以及加工顺序(位置)等因素的影响而不可能始终是恒定的.此产生一类重要的新型排序问题—工件加工时间非恒定的排序问题.一般来说，这类排序问题比经典排序问题更为复杂，绝大多数均为NP-hard问题.而对于NP-hard问题的研究，一般是研究它的多项式时间近似算法，并分析该近似算法的最坏情况界.然而由于生产实践的需要，研究某NP-hard问题一些特例的多项式时间算法是很有必要的.它一方面可以为求出该NP-hard问题一些特例的最优解提供方法，另一方面也可以为解决原NP-hard问题提供近似算法，从而使排序理论更好地服务于生产实践.本文主要对工件加工时间非恒定的排序模型进行了研究.并在以下几个方面做了一些探讨： 1.本文介绍了有关排序问题，计算复杂性，近似算法以及最坏情况界等基本概念，并对近年来出现的各种工件加工时间非恒定的排序模型及其有关结果作了简要的归纳. 2.对工件加工时间是其正常加工时间和开始加工时间的线性函数的排序模型. (1)对目标函数为加工全程的单机排序问题，给出了相应的最优算法；对于加权总完工时间的单机排序问题证明了其为NP-hard的 (2)对机器具有某种优势关系的流水作业排序问题进行了研究，取目标函数分别为加工全程和完工时间之和，对它们分别给出了最优算法. 3.对工件加工时间是其开始加工时间的线性函数的排序模型. (1)对工件间有调整时间和没有调整时间的单机排序问题，以加工全程，加权完工时间之和以及最大延误等为目标函数作了研究，并给出了相应问题的最优算法或者证明了其计算复杂性. (2)对目标函数为极小化最大完工时间和极大化最小机器完工时间的平行机排序问题进行了探讨，分别给出了近似算法并分析了相应的性能比. (3)证明了工件具有调整时间的两台机器的流水作业排序问题是NP-hard的，讨论了机器具有一定优势关系下的一些特殊情况，对目标函数为极小化最大完工时间的情形给出了最优算法. 4.对具有学习效应的排序模型. (1)提出了一种新的具有学习效应的单机排序模型，并对目标函数为极小化最大完工时间，完工时间之和，超前迟后，多目标函数以及一些经典的目标函数的情况进行了研究.并分别给出了最优算法. (2)针对流水作业排序问题，首先研究了目标函数为最大完工时间和完工时间之和的情况，给出了相应问题的近似算法并分析了其性能比.其次对机器具有某种优势关系的情形进行了探讨，对目标函数为最大完工时间问题给出了最优算法.同时还讨论了工件具有线性学习效应的流水作业问题. 5.研究了工件加工时间是其开始加工时间的线性函数的半在线排序模型. 收起

关键词 : 排序工件加工时间非恒定流水作业学习效应最优算法组合优化

3. 一类平行机和批处理机组成的二阶段柔性流水作业问题

[学位论文] 何龙敏上海大学 2005年博士导师: 孙世杰共100页

摘要 : 本文考虑m台同型机(专用机)与一台批处理机组成的二阶段柔性流水作业问题.全文分六章：第一章简述排序与复杂性理论，介绍FSMP(FlowShopwithMultipleProcessors)型问题F2‖f和BI(BurnIn)型问题1|BI|f的各自研究成果，进而引出本文所研究的F2(·... 展开

关键词 : 排序柔性流水作业批处理机复杂性理论最优解

4. 带成组加工的三阶段柔性流水作业加工问题

[学位论文] 吴志刚上海大学 2007年硕士导师: 孙世杰共54页

摘要 : 本文首次研究了以下三阶段柔性流水作业问题，其中阶段 1 m<,1>台同型机组成，阶段2为一台批处理机，可同时加工若干个工件，而阶段3由m<,2>台同型机组成。加工工件必须依次经过阶段1、阶段2和阶段3。以C<,max>为极小化目标函数。对这种NP—hard问题，在加工工件分别... 展开

关键词 : 柔性流水作业同型机近似算法性能比启发式算法

5. 工件加工时间非恒定且工件可拒绝的排序问题

[学位论文] 程予绍上海大学 2008年硕士导师: 孙世杰共51页

摘要 : 排序问题是一类重要的组合优化问题。本文提出一类新型的排序问题--工件加工工时间非恒定且工件可拒绝的排序问题，并对这类问题做了初步研究，具体分为以下几方面； 1. 介绍了有关排序问题，计算复杂性及近似算法等的一些基本概念，并对加工时间... 展开排序问题是一类重要的组合优化问题。本文提出一类新型的排序问题--工件加工工时间非恒定且工件可拒绝的排序问题，并对这类问题做了初步研究，具体分为以下几方面； 1. 介绍了有关排序问题，计算复杂性及近似算法等的一些基本概念，并对加工时间非恒定排序问题及工件可拒绝的排序问题的相关结果做了简要的介绍。同时，阐述了研究加工时间非恒定且工件可拒绝的排序问题理论意义与应用价值。 2.工件加工时间是其开始加工时间的线性函数且工件可拒绝的排序问题。对于最小化最大完工时间与拒绝惩罚和的问题，最小化加权总完工时间与拒绝惩罚和的问题以及最小化最大延迟/延误与拒绝惩罚和的问题，我们分别证明了它们是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。 3.工件加工时间是其基本加工时间和开始加工时间的线性函数且工件可拒绝的排序问题。对于最小化最大完工时间与拒绝惩罚和的问题，我们证明了它是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。对于最小化加权总完工时间与拒绝惩罚和的问题，我们证明了它是NP-困难的，并对它的一个特例设计了多项式时间的最优算法。 4.工件加工时间是其正常加工时间和开始加工时间的线性函数且工件可拒绝的带优势关系流水作业问题。对于最小化最大完工时间与拒绝惩罚和的问题，最小化总完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的最优算法。 5.工件加工时间与工件所排位置有关且工件可拒绝的排序问题。对于最小化最大完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的最优算法。此外，本文还研究了以下加工时间恒定的问题。 1.证明了加工时间恒定的最小化误工工件个数与拒绝惩罚和的排序问题是NP-困难的。 2.约束条件下加工时间恒定的工件可拒绝的排序问题。对于在拒绝惩罚和的约束条件下最小化最大完工时间的问题，在拒绝惩罚和的约束条件下最小化最大延迟/延误的问题，我们分别证明了它们是NP-困难的，并设计了伪多项式时间的最优算法及充分多项式时间近似算法。收起

关键词 : 工件加工时间排序问题

6. 三台机器流水作业中的Lot-Streaming问题

[学位论文] 黄文平上海大学 2002年硕士导师: 孙世杰共47页

摘要 : 该文主要考虑三台机器流水作业中的Lot-Streaming问题(简称LS问题).即一批工件含有N个相同的单元,分成若干批次,各批依次在各台机器间成批转移并在三台机器上加工,每台机器在加工每批工件前可能有不同的调整时间.通过寻求适当的分批数及每批所含单元数... 展开

关键词 : 流水作业 LS问题临界路最优算法 MNP序

7. 稳定性分析和加工时间可变的排序问题

[学位论文] 姜振多上海大学 2007年硕士导师: 孙世杰共43页

摘要 : 本文主要研究了一些具有多项式时间算法排序问题的稳定性和加工时间可变的排序问题，其主要内容为：一、分析了单机和流水作业中一些具有多项式时间算法排序问题的稳定性，即当一些关键参数(加工时间，准备时间)发生变化时最优序是否保持不变? ... 展开

关键词 : 稳定性分析流水作业成组加工

8. 具有调整时间的多工件组成的产品加工问题

[学位论文] 王玉青上海大学 2006年硕士导师: 孙世杰共42页

摘要 : 本文考虑的是有调整时间的多工件组成的产品加工问题：每一产品由若干个工件组成，任一产品的完工时间定义为其所含全部工件完工时的时间，加工一批同类工件前可能需要不同的调整时间.我们主要研究了单机加工条件下，每一产品由m个不同类的普通工件和... 展开

关键词 : 排序调整时间成批加工动态规划算法近似算法性能比产品加工

9. 货物装卸中带共同宽容期的排序问题

[学位论文] 陆焱萍上海大学 2006年硕士导师: 孙世杰共41页

摘要 : 排序论作为运筹学的一个分支，作为一门应用科学，有着深刻的实际背景和广阔的应用前景。随着研究者对排序问题越来越多的关注，各类新型排序也不断地涌现出来。准时生产制和宽容交货期问题就是其中很重要的一部分。本文考虑的是从下述问题中归... 展开

关键词 : 货物装卸排序共同宽容交货期奖赏惩罚动态规划算法分枝定界算法

10. 订单带多类工件加工时的极小迟后范围问题

[学位论文] 陈跃上海大学 2004年硕士导师: 孙世杰共41页

摘要 : 本文考虑了下述由多类工件组成的订单的单机排序问题:每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类.当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间s<,i>,每一订单有一给定的应交工时间.订单的完工时间定义为该... 展开本文考虑了下述由多类工件组成的订单的单机排序问题:每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类.当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间s<,i>,每一订单有一给定的应交工时间.订单的完工时间定义为该订单所含全部工件完工时的时间.我们希望适当排列这n个工件,使得同订单有关的某目标函数达最优值.我们将此类问题称之为订单问题,记为1|s<,f>,order|g,其中s<,f>指机器加工不同类工件前存在调整时间,order表示订单问题,g是目标函数.由于在生产现实中平等对待所有客户的问题十分重要,因此我们考虑的目标函数是使订单的迟后范围最小,即[L<,max>(DC<,i>)-L<,min>(DC<,i>)]的极小化.相应这一排序问题,在第二、三、四章中依不同的背景,我们给出了三种模式.第二章涉及的模式是同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,文中用GT,Ba来表示.我们证明了当目标函数是maxL<,min>(OC<,i>)时,该问题是NP-hard的.在此基础上证明了问题1|s<,f>,order,GT,Ba|L<,max>(DC<,i>)-L<,min>(OC<,i>)是NP-hard的,给出了一分枝定界方法并用实例加以说明.第三章中涉及的模式是同类工件一起连续加工,工件的完工时间为其本身,文中用GT,Ja来表示此种模式.在这种模式下,我们仍然可以证明1|s<,f>,order,GT,Ja| maxL<,min>(OC<,i>)是NP-hard的.然后我们证明了问题1| s<,f>,order,GT,Ja|L<,max>(OC<,i>)-L<,min>(OC<,i>)也是NP-hard的.在本章最后提出了一分枝定界方法,并用实例加以说明.第四章中涉及的模式是同类工件不必一起连续加工,工件的完工时间为其本身,文中用Ja来表示.可以发现1|s<,f>,order,Ja|<,max>L<,min>(OC<,i>)是NP-hard的,类似地,1|s<,f>,order,Ja|L<,max>(OC<,i>)-L<,min>(OC<,i>)也是NP-hard的.对于该问题仍然用分枝定界法来解决. 收起

关键词 : 排序订单问题迟后范围 NP-hard 分枝定界算法