帶時間延遲的排序問題綜述

王煥男

摘 要：近年來，排序問題受到多數學者的重視。同時，在理論和實際方面出現很多新模型.關于多工序的工件排序中，通常認為前面的工序完成之后，后面的工序便可開始加工；可是現實并非如此，各工序之間也需要一定的時間延遲。文章介紹了帶時間延遲排序問題的研究現狀及相關算法。

關鍵詞：排序問題；最優算法；延遲

引言

對于帶有時間延遲的排序問題，可分為兩類，一類是對工件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.