摘 要：文章主要研究帶精確延遲時間的排序問題，目標是極小化加權(quán)總完工時間，分別給出了單臺機和兩臺流水作業(yè)的最優(yōu)算法。

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

引言

精確時間延遲排序問題按機器數(shù)量分為單機問題和兩臺機流水作業(yè)問題。用三參數(shù)分別表示為1|exact lj|Cmax，F(xiàn)2|exact lj|Cmax。本文主要研究帶精確時間延遲的單機排序問題和兩臺機流水作業(yè)排序問題。每個工件Jj（j=1，2，…，n）有兩道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工時間c與第二道工序的開始時間S之間存在一個精確的延遲時間，即S=c+lj。所有工序操作時間都相等aj=bj=a，且精確延誤時間是工序操作時間的整數(shù)倍lj=ka（k∈N+） 。

現(xiàn)有文獻考慮的目標函數(shù)大多是以最小化時間表長（makespan）為目標函數(shù).本文所考慮的目標函數(shù)是最小化加權(quán)總完工時間（？撞wjCj）。

1 預(yù)備結(jié)果

下面先給出相關(guān)的定義以及一些初步的結(jié)論。

定義1.1 將k個工件的第一道工序連續(xù)加工，再按照第一道工序的加工順序連續(xù)加工這k個工件的第二道工序。

當(dāng)?shù)趉個工件的第一道工序ak的完工時間與第一個工件的第二道工序b1的最早開工時間之間存在被迫空閑時，我們稱之為被迫不連續(xù)加工（圖1）。

圖1 被迫不連續(xù)加工

引理1.1 最優(yōu)排序中，只存在被迫不連續(xù)加工和？資+1-連續(xù)加工這兩種加工方式，即不存在m（m>k+1或m

證明：用反證法證明。

假設(shè)最優(yōu)排序中將工件進行m-連續(xù)加工。當(dāng)m>k+1時，精確延遲時間大于ka；當(dāng)m

由于我們所研究問題的精確延遲時間為ka，所以得出矛盾。

即最優(yōu)排序中，只存在被迫不連續(xù)加工和？資+1-連續(xù)加工這兩種加工方式，即不存在m（m>k+1或m

引理1.2 如果最優(yōu)排序中存在被迫不連續(xù)加工的工件，則這些工件必在連續(xù)加工的工件之后進行加工。

證明：假設(shè)在A時刻有一組不連續(xù)加工的工件，不妨設(shè)這組工件中有m（m

由圖1可知，這m個工件的完工時間為一組等差數(shù)列。

因此，如果最優(yōu)排序中存在被迫不連續(xù)加工的工件，則這些工件必在連續(xù)加工的工件之后進行加工。

2 主要結(jié)果

本節(jié)主要研究帶精確時間延遲的極小化加權(quán)總完工時間問題，每個工件記為Jj（aj，bj，lj，wj），目標函數(shù)為加權(quán)總完工時間。單機問題三參數(shù)表示為 ；兩臺機流水作業(yè)問

題三參數(shù)表示為 。

算法H1

（1）將所有工件重新排序，使w1？叟w2？叟…？叟wn；

（2）再按照J1，J2，…，Jn的順序?qū)⒐ぜ纸M，每組中有k+1個工件；

（3）進行？資+1-連續(xù)加工工件；

（4）當(dāng)工件個數(shù)不足k+1個時，將這些工件進行被迫不連續(xù)加工。此時單機問題，機器會出現(xiàn)空閑。

定理2.1 算法H1是上述問題的最優(yōu)算法。

證明：首先證明算法H1是單機問題的最優(yōu)算法。

由于我們研究的是精確時間延遲排序，即每個工件第一道工序的完工時間c與第二道工序的開始時間S之間存在一個精確的延遲時間，當(dāng)工件第一道工序的開始時間確定時，第二道工序的開始時間也相應(yīng)確定；因此，我們只需要排好每個工件的第一道工序。

下面用反證法分步證明。

（1）顯而易見，最優(yōu)排序中工件J1，J2，…，Jn是按w1？叟w2？叟…？叟wn的順序加工的。

（2）當(dāng)工件的個數(shù)是k+1的整數(shù)倍時，證明最優(yōu)排序是將工件J1，J2，…，Jn進行k+1-連續(xù)加工；當(dāng)工件的個數(shù)不是？資+1的整數(shù)倍時，證明最優(yōu)排序是先將工件J1，J2，…，Jn進行k+1-連續(xù)加工，再將最后一組工件進行被迫不連續(xù)加工。

由引理1.1和引理1.2可知，最優(yōu)排序中，只存在被迫不連續(xù)加工和k+1-連續(xù)加工這兩種加工方式，如果最優(yōu)排序中存在被迫不連續(xù)加工的工件，則這些工件必在連續(xù)加工的工件之后進行加工。結(jié)合我們的算法，只需證明最優(yōu)排序不可能存在兩組或者兩組以上被迫不連續(xù)加工的工件。

不妨假設(shè)在A時刻有兩組相鄰的被迫不連續(xù)加工的工件，第一組中有m個工件，第二組中有n個工件。現(xiàn)將這兩組工件放在一起加工，比較這兩組工件在前后兩種排序中的總完工時間。將這兩組工件不放在一起加工時每組的完工時間分別為

現(xiàn)在考慮將這兩組工件不放在一起加工時，這m+n個工件的總完工時間為

而將這兩組工件放在一起加工時，總完工時間分為m+nk+1三種情況。

情形一：當(dāng)m+n

情形二：當(dāng)m+n=k+1時，將這兩組工件放在一起加工，變?yōu)橐唤Mk+1-連續(xù)加工工件。這m+n個工件的總完工時間為

比較這兩個總完工時間知

情形三：當(dāng)m+n>k+1時，將這兩組工件放在一起加工，變?yōu)橐唤Mk+1-連續(xù)加工工件和一組被迫不連續(xù)加工工件；這組被迫不連續(xù)加工的工件個數(shù)為m+n-k-1個。

這m+n個工件的總完工時間為

比較這兩個總完工時間知

由2-（5）、2-（7）、2-（9）式可知，將第二組被迫不連續(xù)加工的工件前移，總完工時間不會變大。即最優(yōu)排序不可能存在兩組或者兩組以上被迫不連續(xù)加工的工件。

綜上所述，算法H1是單機問題的最優(yōu)算法。

顯而易見，算法H1是兩臺機流水作業(yè)的最優(yōu)算法。最優(yōu)排序如圖2所示。

圖2 最優(yōu)排序

3 結(jié)束語

本文主要研究帶精確時間延遲的單機排序問題和兩臺機流水作業(yè)排序問題并給出了最優(yōu)算法。

參考文獻

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

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

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

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

[5]Farina A， Neri P. Multitarget interleaved tracking for phased array radar， IEEE Proc. Part F： Comm. Radar Signal Process. 127（4），1980.312-318.

[6]Izquierdo-Fuente A， Casar-Corredera J R. Optimal radar pulse scheduling using neural networks， in： IEEE International Conference on Neural Networks. vol. 7，1994.4588-4591.

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

[8]Ageev AA， Kononov AV. Approximation algorithms for the single and two- machine scheduling problems with exact delays. Operations Research Letters，2007，35（4）：533-540.

作者簡介：王煥男（1986，5-），女，黑龍江省海倫市人，碩士研究生，助教，主要從事組合優(yōu)化的研究。