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

王煥男

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

關(guān)鍵詞：排序問題；最優(yōu)算法；延遲

引言

對于帶有時間延遲的排序問題，可分為兩類，一類是對工件Jj的兩道工序間至少需要延遲lj個單位時間，我們稱這類問題為至少時間延遲排序。另一類是前后兩道工序間時間延遲剛好為lj個單位時間（exact delay），我們稱這類問題為精確時間延遲排序。目前，關(guān)于以上這兩類問題的研究，主要集中于單臺機和兩臺機的流水作業(yè)問題，并且，多數(shù)以極小化最大完工時間為目標（makespan），考慮總完工時間的文獻很少。

多工序排序問題可以分為無時間延遲（lj=0）流水作業(yè)排序問題，帶有至少lj個單位時間延遲的排序問題，帶有精確時間延遲的排序問題。

1 無時間延遲排序問題

對兩臺機流水作業(yè)問題F2|no-wait|Cmax，Johnson給出了一個O（n log n）的最優(yōu)算法。對目標函數(shù)是最小化總完工時間問題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對無時間延遲兩臺機流水作業(yè)排序問題提出一個工件插入啟發(fā)式算法（insertion heuristic）。Chen et al. 對無時間延遲兩臺機流水作業(yè)排序問題提出一個遺傳算法和一些計算結(jié)果。Fink 和 Voβ對無時間延遲m臺機流水作業(yè)排序問題提出一個元啟發(fā)式算法（metaheuritics）。

2 至少時間延遲排序問題

以makespan為目標的單臺機排序問題，在解不限于排列排序的情況下，Kern和Nawijn證明是NP-難的，而Lenstra證明兩臺流水作業(yè)排序問題F2|lj|Cmax是強NP-難的，DellAmico給出該問題一個2-近似多項式時間算法， 并且提出一個禁忌搜索算法。當兩道工序加工時間相同時，DellAmico、Vaessens證明F2|lj，aj=bj|Cmax是強NP-難的。Johnson、Mitten 證明了該問題存在最優(yōu)排列排序（permutation schedule）；當工件延遲時間相等時， Johnson、Mitten 證明該問題存在一個最優(yōu)排序是排列排序（permutation schedule）。當兩道工序加工時間相同且時間延遲lj{0，l}時，Yu證明F2|lj∈{0，1}，aj=bj|Cmax是強NP-難的。進一步，即便兩道工序的加工時間均為單位時間，Yu證明問題F2|ljaj=bj=1|Cmax仍是強NP-難的。

3 精確時間延遲排序問題

當?shù)谝坏拦ば蚺c第二道工序的加工時間分別等于兩個定值時，文獻Farina 和Neri對問題1|exact lj|Cmax的一種特殊情況提出了一個貪婪算法；Izquierdo-Fuente和Casar-Corredera則對該問題提出了一個神經(jīng)網(wǎng)絡(luò)算法。單臺機的一些特殊情況，Orman和Potts證明是多項式可解的，并且證明即使所有工序加工時間相同，該問題仍然是強NP-難的。Elshafei et al.基于離散化的時間跨度問題提出一個拉格朗日松弛算法（Lagrange relaxation algorithm）。Leung等利用貪婪算法研究延誤非增的情形，給出了問題F2|lj，aj=a，bj=b，a3b|Cj的最優(yōu)排序，而對問題F2|lj，aj=a，bj=b，a

4 結(jié)束語

本文主要介紹了帶有時間延遲的排序問題。目前國內(nèi)外研究現(xiàn)狀如表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.