二台机器自由作业总流程的一种改进方法

基于1992年M.Dror提出的工件加工时间依赖机器的排序问题,研究以最大完工时间和以总完工时间为优化目标的两类排序问题。二台机器自由作业总流程问题为NP-困难问题,加工时间仅依赖于机器的两台机器自由作业排序问题可转化成指派问题,并且可以构造出这一问题的显式解。文章利用不允许机器空闲的条件下该问题的最优解,给出允许机器空闲而使完工时间总和减少的一种方法,说明在一定条件下不允许机器空闲的显式解一定不是允许机器空闲的显式解。

平行机及自由作业的排序与转包

研究工件排序与转包相联的模型,即制造商从客户处接受一批工件,这些工件既可以由制造商加工,也可以一定费用转包给承包商加工.制造商需要确定被转包的工件集及工件的加工顺序,使得加工费用和转包费用之和为最小.研究制造商为平行机及自由作业,承包商为单机情况下的排序与转包模型,基于动态规划算法给出了近似算法,并分析了该算法的性能比.

自由作业环境下的供应链排序

本文研究了一类集成工件加工和发送的供应链排序模型.利用排序理论和动态规划方法,获得了两机器情形下的供应链排序问题的多项式时间近似算法,并证明算法的性能比为2.

加工时间依赖于机器的自由作业排序问题

1992年M．Dror提出工件的加工时间依赖于机器的排序问题（schedulingwithmachinedependentprocessingtimes），并研究以最大完工时间（makespan）和以总的完工时间为优化目标的两种这类排序问题．然而，M．Dror对以总的完工时间为优化目标提出的“最优算法”是错误的．本文用算例表明他提出的算法不是最优的，并在机器连续加工的条件下，把这个排序问题转化成指派问题（assignmentproblem），从而可以用匈牙利算法得到最优解．最后，我们提出几个尚未解决的问题，以期引起国内外同行进一步研究．

带准备时间的自由作业排序问题——最坏性能比分析

本文研究了一类自然的排序问题，带准备时间的自由作业（ＯｐｅｎＳｈｏｐ）排序．在机器台数任意的情况下，证明了一个简单的贪婪算法的最坏性能比不超过２，并猜想该算法的紧界为２－１ｍ，其中ｍ为机器台数．特别当ｍ＝２时。

自由作业稠密时间表的性能比上界

对于自由作业问题 ,如果从初始时刻开始 ,逐步在每个机器安排任一可以加工的工件 ,避免不必要的空闲 ,所得的安排称为稠密时间表。其加工总长与最优值之比具有上界 2 - 1 /m(m为机器数 ) ,是一个尚未证明的猜想。本文引入了最后工件组及相关机器集的概念 ,证明了 m=5时该猜想是成立的。

一类自由作业供应链排序的研究

本文研究一类集成工件生产和发送的排序模型。在该模型中,供应链的上游首先将工件安排在自由作业机器上加工,然后把加工完毕的工件分批发送给下游。问题是寻找生产和发送相连的排序,使得生产排序费用和发送费用总和最少。这里,生产排序费用是以工件带权送到时间和表示;发送费用由固定费用和与运输路径有关的变化费用组成。在指出问题的NP困难性后,本文用动态规划算法构造了一致条件下的多项式时间近似算法,并分析算法的性能比。本文最后还讨论了该问题的其它情形。

关于一类自由作业机器排序问题

文章研究文［１］中提出的加工时间依赖于机器的自由作业排序问题。Ｍ．Ｄｏｒｏｒ在［１］中提出了一个算法（算法３．４）。最近，Ａ．Ｊ．Ｖａｋｈａｒｉａ、Ｂ．Ｃａｔａｙ［２］及项思明、唐国春［３］均指出Ｍ．Ｄｏｒｏｒ的算法不是最优的。项思明和唐国春提出对这类问题在机器连续加工情形下的一种求解方法，即将排序问题化成指派问题。本文对这种解法作了简化，并回答文［３］中提出的几个问题。

自由作业稠密时间表的操作链性质分析

对于自由作业加工全长问题,研究了稠密时间表操作链的两个性质。作为应用,利用此性质及有关文献的结果,给出机器数为6的稠密时间表性能比猜想的证明。

关于工件组的两机自由作业时间表问题

讨论关于工件组的两机自由作业时间表的加工全长问题。无论是对于成组加工情形还是分组情形 ,该问题都可以被证明是 NP困难的。对于成组加工的情形 ,设计了一个性能比为 5/4的近似算法 ,该算法生成的时间表作为分组情形的解 ,性能比仍能保持为 5/4。此外 ,还讨论了如何最优地求解只有一个工件组的情形。

工件有到达时间的两机器自由作业稠密时间表(英文)

对于两机器自由作业加工总长问题,工件带有到达时间,我们证明了稠密时 间表的性能比为1.5.

依赖机器的两台机自由作业排序问题

研究加工时间仅依赖于机器的两台机自由作业排序问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|ΣC_j.项思明和唐国春(1998)证明了可将该问题转化成指派问题.俞文(?)和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解.将给出问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|∑C_j的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解.

关于一类两台机器自由作业的排序问题

以工件完工时间的总和为优化目标的两台机器自由作业问题是NP-hard问题.本文针对加工时间仅依赖于机器并且机器连续加工的问题,给出了机器排序是可行排序的充分必要条件,引入可行排列的极小子排列的概念,运用组合优化方法,研究了最优排序中极小子排列的性质,并由此得到了该问题的最优时间表的一般构造方法.

加工时间成比例的两阶段自由作业排序问题

对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究.工件需要分别在包含m1和m2台平行机的两阶段中进行加工,工件在阶段间的加工满足自由作业环境要求,且相同工件在两阶段的加工时间相同,目标是极小化时间表长,即最后完工工件的完工时间.证明了当min{m1,m2}≥2时该问题是NP-难的,给出了该问题的一个近似算法,并证明了该算法的最坏情况界不大于3/2-3/2(2min{m1,m2}+1).得到了当min{m1,m2}=1时,该算法为问题的最优算法.

退化工件误工数的双机自由作业排序问题

探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题,其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是NP困难的;然后对最小化加权误工工件数问题给出了一个拟多项式时间算法;最后对几种特殊情形给出了多项式时间算法。

使带权总完工时间为最小的自由作业排序问题

本文研究多工序排序中的一类自由作业模式。对于使机器带权总完工时间为最小或者使工件带权总完工时间为最小的两类问题,本文用组合方法或者数学规划方法分别给出了稠密时间表的算法或者置换排序的算法,并分析算法的性能比。此方法在理论和应用两方面都是有意义的。

二台机器自由作业总流程的一些性质

二台机器自由作业总流程问题是NP-困难的,对于加工时间仅依赖于机器的情形在不允许机器空闲的条件下存在显式解.对于O2│pij=pi│∑Cj,利用在不允许机器空闲的条件下该问题的显式解给出允许机器空闲条件下解的一些性质.

自由作业加工总长排序问题的稠密时间表

研究自由作业加工总长排序问题稠密时间表的性能比。通过定义工件和机器的状态函数,得到稠密时间表关于性能比猜想对于任何机器数m都成立的充分条件,并应用这个条件,大大地减化了有关文献的证明过程。本文最后还研究对于任何机器数m稠密时间表猜想都成立的两种情况。

最后完工机器至多两个空闲的自由作业稠密时间表(英文)

对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的2-1/m倍,是一个在机器数m>6时尚未被证明的猜想.本文通过引入工件与机器特征函数及机器关于工件非间断等概念,研究当最后完工机器至多有两个空闲区间时,性能比猜想成立的充分条件.

具有优先权的自由作业时间表问题研究

研究了具有优先权的自由作业时间表问题,在工件具有准备时间的条件下,给出一种新的启发式算法,其最坏性能比不超过2,猜想该算法的紧界是2-2/(m+1),其中m是机器的台数.证明在3台机器的情况下,该算法的最坏性能比为3/2,且上界是紧的.