帶時(shí)間延遲的排序問題綜述

王煥男

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

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

引言

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

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

1 無時(shí)間延遲排序問題

對(duì)兩臺(tái)機(jī)流水作業(yè)問題F2|no-wait|Cmax，Johnson給出了一個(gè)O（n log n）的最優(yōu)算法。對(duì)目標(biāo)函數(shù)是最小化總完工時(shí)間問題F2|no-wait|Cj，van Deman和Baker提出一個(gè)分支定界算法；Rck證明了這個(gè)問題是強(qiáng)NP-難的。當(dāng)每個(gè)工序的操作時(shí)間Pi，j{0，1}時(shí)，Gonzales證明F|no-wait，Pi，j{0，1}|Cj是強(qiáng)NP-完全問題；兩臺(tái)時(shí)，Sriskar

ajah和Ladet證明F2|no-wait，Pi，j{0，1}|Cj多項(xiàng)式時(shí)間可解。Rajendran 和 Chaudhuri對(duì)無時(shí)間延遲兩臺(tái)機(jī)流水作業(yè)排序問題提出一個(gè)工件插入啟發(fā)式算法（insertion heuristic）。Chen et al. 對(duì)無時(shí)間延遲兩臺(tái)機(jī)流水作業(yè)排序問題提出一個(gè)遺傳算法和一些計(jì)算結(jié)果。Fink 和 Voβ對(duì)無時(shí)間延遲m臺(tái)機(jī)流水作業(yè)排序問題提出一個(gè)元啟發(fā)式算法（metaheuritics）。

2 至少時(shí)間延遲排序問題

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

3 精確時(shí)間延遲排序問題

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

4 結(jié)束語

本文主要介紹了帶有時(shí)間延遲的排序問題。目前國內(nèi)外研究現(xiàn)狀如表1所示。

參考文獻(xiàn)

[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.