带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

带有不可用区间的单机排序问题

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。一个工件或者被拒绝加工,或者被接受。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。在张丽琦工作的基础上增加了一个不可用区间,机器在此区间内不能加工工件,并且在同一时刻至多加工一个工件。目标函数是最小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出一个动态规划算法,然后通过构造输入,将拒绝惩罚进行取整运算,再通过动态规划算法,得到拒绝惩罚取整后的一个最优排序,按照这个工件排序得到原问题的一个可行排序,最后借助一个3—因子算法得到一个全多项式时间近似方案。     

加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

时间相关的单机排序的最坏竞争比分析

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题.工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工.本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比.进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法.     

一类单机排序问题的算法研究

本文讨论了加工时间依赖于开工时间的单机排序问题。在这一模型中每个工件具有一个基本加工时间。本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论,对某些特殊情况给出了多项式算法。     

批处理机上有就绪和截止时间的等长度工件排序

一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题,目标是求一个可行时间表.就该问题,Baptiste已经提出了一个复杂性为O(n8)的算法,在此基础上,本文推广Garey等人关于对应的经典排序问题的算法,得到了一个复杂性为O(n2)的算法.算法分两个阶段执行:在阶级I,算法找出所谓的禁止开工区间,在这些区间中将不允许有工件开工;在阶段II,算法从时刻零开始,每当机器有空闲且不属于禁止开工区间的时候,就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工,若当前的机器空闲时刻属于某个禁止开工区间,则首先更新其到该禁止开工区间的右端点再进行决策.     

带到达时间的加工时间离散可控的单机排序问题1|rj , dm|Cmax +TPC的FPTAS算法

考虑工件加工时间离散可控的单机分批排序问题,目标函数是极小化最大完工时间与加工费用之和.对于工件不同时到达的情况,本文给出了FPTAS算法.     

工时随开工时间递增的成组排序问题

讨论了一类工件的加工时间随工件的开工时间线性递增的成组排序问题1|pij=bij aijt,S=sf,GT|Cmax,给出了求最优解的多项式时间算法.     

基于遗传算法的Job Shop静态调度算法

研究了具有柔性加工路径的Ｊｏｂ Ｓｈｏｐ静态调度问题，并考虑了与操作序列有关的工件安装时间和工件到期时间的约束。提出了一种将遗传算法和分派规则相结合的调度算法，用遗传算法决定各工件的每个操作应分配到哪台机器上加工，而对每台机器则运用分派规则来决定相应工件在此机器上加工的次序和开始加工时间，遗传算法中的进化机理使得该算法有可能得到最优调度结果。最后给出了此调度算法的仿真结果。     

带准备时间的任务单机学习效应排序问题

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响．研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间．这个问题是NP-难问题．用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界．计算结果表明分支定界法和启发式算法求解此问题非常有效．     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

工件可拒绝的分批配送问题研究

考虑工件可拒绝的分批配送问题:一个制造商为一个客户加工n个工件,每个工件既可以被接受加工,也可以被拒绝加工(但要支付拒绝费用),工件加工完之后要安排车辆运送给客户,完工时间为工件送达客户的时间.目标函数为被接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,文中对处理机为单机的情形给出了多项式时间算法,且证明了两台平行机的情形下该问题是NP-完备的,并给出了伪多项式时间算法.     

交货时间区间内加权完工工件个数最大的分批排序算法

讨论了只有一台批处理机时,在交货期区间内使加权完工工件数最大的分批排序问题,给出了求解这一问题的动态规划算法.     

两个带有分批费用的单机平行分批排序问题

假定工件和批处理机都在零时刻到达,工件被成批进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用。第1个问题对目标函数为任意的正则函数与分批费用之和的情形,利用动态规划方法给出了拟多项式时间算法;第2个问题对目标函数为误工工件数与分批费用之和的极小化问题,同样利...     

单机上考虑运输的退化工件的在线排序问题

研究了单台机器上工件具有可退化效应并考虑工件运输的在线排序问题.工件按时间在线到达.这些工件先在机器上加工,完工的工件再由一台运输车辆将其运送给顾客.排序问题的目标是最小化最大运输完工时间.对于所讨论的排序模型,给出了问题的下界并给出达到下界的最好可能的在线算法.     

误工排序问题的研究

误工排序问题是经典排序论中最基本和最重要的问题.40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现.本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义.这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果.     

平行批排序最小化最大完工时间在线算法的一个注记

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5 1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1 α)r αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.