王焕男

摘 要：近年來，排序问题受到多数学者的重视。同时，在理论和实际方面出现很多新模型.关于多工序的工件排序中，通常认为前面的工序完成之后，后面的工序便可开始加工；可是现实并非如此，各工序之间也需要一定的时间延迟。文章介绍了带时间延迟排序问题的研究现状及相关算法。

关键词：排序问题；最优算法；延迟

引言

对于带有时间延迟的排序问题，可分为两类，一类是对工件Jj的两道工序间至少需要延迟lj个单位时间，我们称这类问题为至少时间延迟排序。另一类是前后两道工序间时间延迟刚好为lj个单位时间（exact delay），我们称这类问题为精确时间延迟排序。目前，关于以上这两类问题的研究，主要集中于单台机和两台机的流水作业问题，并且，多数以极小化最大完工时间为目标（makespan），考虑总完工时间的文献很少。

多工序排序问题可以分为无时间延迟（lj=0）流水作业排序问题，带有至少lj个单位时间延迟的排序问题，带有精确时间延迟的排序问题。

1 无时间延迟排序问题

对两台机流水作业问题F2|no-wait|Cmax，Johnson给出了一个O（n log n）的最优算法。对目标函数是最小化总完工时间问题F2|no-wait|Cj，van Deman和Baker提出一个分支定界算法；Rck证明了这个问题是强NP-难的。当每个工序的操作时间Pi，j{0，1}时，Gonzales证明F|no-wait，Pi，j{0，1}|Cj是强NP-完全问题；两台时，Sriskar

ajah和Ladet证明F2|no-wait，Pi，j{0，1}|Cj多项式时间可解。Rajendran 和 Chaudhuri对无时间延迟两台机流水作业排序问题提出一个工件插入启发式算法（insertion heuristic）。Chen et al. 对无时间延迟两台机流水作业排序问题提出一个遗传算法和一些计算结果。Fink 和 Voβ对无时间延迟m台机流水作业排序问题提出一个元启发式算法（metaheuritics）。

2 至少时间延迟排序问题

以makespan为目标的单台机排序问题，在解不限于排列排序的情况下，Kern和Nawijn证明是NP-难的，而Lenstra证明两台流水作业排序问题F2|lj|Cmax是强NP-难的，DellAmico给出该问题一个2-近似多项式时间算法， 并且提出一个禁忌搜索算法。当两道工序加工时间相同时，DellAmico、Vaessens证明F2|lj，aj=bj|Cmax是强NP-难的。Johnson、Mitten 证明了该问题存在最优排列排序（permutation schedule）；当工件延迟时间相等时， Johnson、Mitten 证明该问题存在一个最优排序是排列排序（permutation schedule）。当两道工序加工时间相同且时间延迟lj{0，l}时，Yu证明F2|lj∈{0，1}，aj=bj|Cmax是强NP-难的。进一步，即便两道工序的加工时间均为单位时间，Yu证明问题F2|ljaj=bj=1|Cmax仍是强NP-难的。

3 精确时间延迟排序问题

当第一道工序与第二道工序的加工时间分别等于两个定值时，文献Farina 和Neri对问题1|exact lj|Cmax的一种特殊情况提出了一个贪婪算法；Izquierdo-Fuente和Casar-Corredera则对该问题提出了一个神经网络算法。单台机的一些特殊情况，Orman和Potts证明是多项式可解的，并且证明即使所有工序加工时间相同，该问题仍然是强NP-难的。Elshafei et al.基于离散化的时间跨度问题提出一个拉格朗日松弛算法（Lagrange relaxation algorithm）。Leung等利用贪婪算法研究延误非增的情形，给出了问题F2|lj，aj=a，bj=b，a3b|Cj的最优排序，而对问题F2|lj，aj=a，bj=b，a

4 结束语

本文主要介绍了带有时间延迟的排序问题。目前国内外研究现状如表1所示。

参考文献

[1]Johnson S， Discussion M. Sequencing n jobs on two machines with arbitrary time-lags[J]. Management Science，1958，5：299-303.

[2]Lenstra J K. Private communication，1991.

[3]Dell'Amico M. Shop problems with two machines and time lags[J].Operations Research，44，1996.

[4]Pinedo M. Scheduling： Theory algorithms and Systems[M].2nd ed. Prentice Hall，2002.

[5]Leung J， Li H， Zhao H. Scheduling two-machine flow shops with exact delay[J]. International Journal of Foundations of Computer Science，2007，18（2）： 341-360.

[6]Ageev AA， Kononov AV. Approximation algorithms for scheduling problems with exact delays. In： Proceedings of the fourth international workshop， WAOA 2006， Zurich， Switzerland， 2006：1-14.

[7]Huo Y， Li H， Zhao H. Minimizing total completion time in two-machine flow shops with exact delays[J].Computers and Operations Research， 2009，36（6）： 2018-2030.

[8]Glascock J，Hunter B. Minimizing total completion time in two-machine flow shops with exact delay using genetic algorithm & ant colony algorithm， GECCO， 2009：2733-2736.