带时间延迟的排序问题综述

《带时间延迟的排序问题综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、带时间延迟的排序问题综述　　摘要：近年?恚?排序问题受到多数学者的重视。同时，在理论和实际方面出现很多新模型.关于多工序的工件排序中，通常认为前面的工序完成之后，后面的工序便可开始加工；可是现实并非如此，各工序之间也需要一定的时间延迟。文章介绍了带时间延迟排序问题的研究现状及相关算法。　　关键词：排序问题；最优算法；延迟　　引言　　对于带有时间延迟的排序问题，可分为两类，一类是对工件Jj的两道工序间至少需要延迟lj个单位时间，我们称这类问题为至少时间延迟排序。另一类是前后两道工序间时间延迟刚好为lj个单位时间（

2、exactdelay），我们称这类问题为精确时间延迟排序。目前，关于以上这两类问题的研究，主要集中于单台机和两台机的流水作业问题，并且，多数以极小化最大完工时间为目标（makespan），考虑总完工时间的文献很少。　　多工序排序问题可以分为无时间延迟（lj=0）流水作业排序问题，带有至少lj个单位时间延迟的排序问题，带有精确时间延迟的排序问题。　　1无时间延迟排序问题　　对两台机流水作业问题F2

3、no-wait

4、Cmax，Johnson给出了一个O（nlogn）的最优算法。对目标函数是最小化总完工时间问题F2

5、

6、no-wait

7、Cj，vanDeman和Baker提出一个分支定界算法；Rck证明了这个问题是强NP-难的。当每个工序的操作时间Pi，j{0，1}时，Gonzales证明F

8、no-wait，Pi，j{0，1}

9、Cj是强NP-完全问题；两台时，Sriskar　　ajah和Ladet证明F2

10、no-wait，Pi，j{0，1}

11、Cj多项式时间可解。Rajendran和Chaudhuri对无时间延迟两台机流水作业排序问题提出一个工件插入启发式算法（insertionheuristic）。Chenetal.对无时间延迟

12、两台机流水作业排序问题提出一个遗传算法和一些计算结果。Fink和Voβ对无时间延迟m台机流水作业排序问题提出一个元启发式算法（metaheuritics）。　　2至少时间延迟排序问题　　以makespan为目标的单台机排序问题，在解不限于排列排序的情况下，Kern和Nawijn证明是NP-难的，而Lenstra证明两台流水作业排序问题F2

13、lj

14、Cmax是强NP-难的，Dell’Amico给出该问题一个2-近似多项式时间算法，并且提出一个禁忌搜索算法。当两道工序加工时间相同时，Dell’Amico、Vaesse

15、ns证明F2

16、lj，aj=bj

17、Cmax是强NP-难的。Johnson、Mitten证明了该问题存在最优排列排序（permutationschedule）；当工件延迟时间相等时，Johnson、Mitten证明该问题存在一个最优排序是排列排序（permutationschedule）。当两道工序加工时间相同且时间延迟lj{0，l}时，Yu证明F2

18、lj∈{0，1}，aj=bj

19、Cmax是强NP-难的。进一步，即便两道工序的加工时间均为单位时间，Yu证明问题F2

20、ljaj=bj=1

21、Cmax仍是强NP-难的。　　

22、3精确时间延迟排序问题　　当第一道工序与第二道工序的加工时间分别等于两个定值时，文献Farina和Neri对问题1

23、exactlj

24、Cmax的一种特殊情况提出了一个贪婪算法；Izquierdo-Fuente和Casar-Corredera则对该问题提出了一个神经网络算法。单台机的一些特殊情况，Orman和Potts证明是多项式可解的，并且证明即使所有工序加工时间相同，该问题仍然是强NP-难的。Elshafeietal.基于离散化的时间跨度问题提出一个拉格朗日松弛算法（Lagrangerelaxationalgo

25、rithm）。Leung等利用贪婪算法研究延误非增的情形，给出了问题F2

26、lj，aj=a，bj=b，a3b

27、Cj的最优排序，而对问题F2

28、lj，aj=a，bj=b，a

29、Cj能得到一个2-近似算法。Ageev和Kononov分别研究了单台机、两台流水作业问题的近似算法。Ageev和Baburin给出了问题1

30、exactlj，aj=bj=1

31、Cmax的一个7/4-近似算法，并且证明了界是不可改进的，同时，给出问题F2

32、exactlj，aj=bj=1

33、Cmax的一个3/2-近似算法，Yu证明以上两个问题是强NP-

34、难的。Huo等人、Glascock、BrianHunter研究了问题F2

35、exactlj

36、Cj的问题的复杂性和启发式算法。　　4结束语　　本文主要介绍了带有时间延迟的排序问题。目前国内外研究现状如表1所示。　　参考文献　　[1]JohnsonS，DiscussionM.Sequencingnjobsontwomachineswitharbitrarytime-lags[J].Manag