帶精確時(shí)間延遲的排序問(wèn)題

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

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

引言

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

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

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

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

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

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

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

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

證明：用反證法證明。

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

由于我們所研究問(wèn)題的精確延遲時(shí)間為ka，所以得出矛盾。

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

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

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

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

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

2 主要結(jié)果

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

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

算法H1

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

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

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

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

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

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

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

下面用反證法分步證明。

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

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

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

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

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

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

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

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

比較這兩個(gè)總完工時(shí)間知

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

這m+n個(gè)工件的總完工時(shí)間為

比較這兩個(gè)總完工時(shí)間知

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

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

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

圖2 最優(yōu)排序

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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