帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)問(wèn)題研究

王煥男

(三亞學(xué)院理工學(xué)院，海南 三亞 572022)

1 引言

關(guān)于帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)問(wèn)題主要成果有：文獻(xiàn)[1](Ageev and Kononov，2006)對(duì)于問(wèn)題F2| exactlj|Cmax設(shè)計(jì)1個(gè)3的近似算法，1.5-ε的難近似界，O(nlogn)時(shí)間內(nèi)可解；對(duì)于問(wèn)題F2|exactlj,aj≤bj|Cmax設(shè)計(jì)1個(gè)2的近似算法，1.5-ε的難近似界，O(nlogn)時(shí)間內(nèi)可解；對(duì)于問(wèn)題F2|exactlj,aj≥bj|Cmax設(shè)計(jì)1個(gè)2的近似算法，1.5-ε的難近似界，O(nlogn)時(shí)間內(nèi)可解。文獻(xiàn)[1](Ageev and Kononov，2006)和[2](Ageev and Kononov，2007)對(duì)一般情況也設(shè)計(jì)了更好的近似算法，他們進(jìn)一步證明了(1.5-ε)-近似算法的存在性，暗示P=NP。文獻(xiàn) [2](Ageev and Baburin，2007)假設(shè)在單位加工時(shí)間下，證明了對(duì)于問(wèn)題F2|exactlj,aj=bj= 1 |Cmax的近似因子是3/2，證明兩臺(tái)機(jī)的算法可以在O(n2logn)時(shí)間內(nèi)實(shí)現(xiàn)。文獻(xiàn)[3](Yu，1996)證明這個(gè)問(wèn)題是強(qiáng)NP-難的。文獻(xiàn)[4](Josh Glascock，Brian Hunter，2009)開(kāi)發(fā)了基于遺傳算法(GA)和蟻群優(yōu)化(ACO)的兩個(gè)元啟發(fā)式算法。文獻(xiàn)[5](Yumei Huo，HaibingLi，HairongZha，2009)研究帶確切延誤的兩臺(tái)機(jī)流水作業(yè)的排列排序，注意到甚至對(duì)于排列排序，這個(gè)問(wèn)題仍然是強(qiáng)NP-難的，證明了對(duì)于一些特殊情況一些簡(jiǎn)單的算法能用于找到最優(yōu)排序。他們?cè)O(shè)計(jì)了第1個(gè)元啟發(fā)式算法，1個(gè)禁忌搜索算法和1個(gè)模擬退火算法解決這個(gè)問(wèn)題。研究帶確切延誤的兩臺(tái)機(jī)流水作業(yè)的排列排序最小化總完工時(shí)間。對(duì)于一般情況，這個(gè)問(wèn)題是NP-難的。研究多項(xiàng)式可解的特殊例子，對(duì)于一般情況開(kāi)發(fā)了一些簡(jiǎn)單啟發(fā)式算法和共通啟發(fā)式演算法。

對(duì)上述研究綜述進(jìn)行匯總?cè)绫?所示。

而本研究主要研究帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)問(wèn)題。每個(gè)工件Jj(j=1,2,…,n)有兩道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工時(shí)間caj與第二道工序的開(kāi)始時(shí)間sbj之間存在一個(gè)精確時(shí)間延遲exactlj，即sbj=caj+lj。所有工序操作時(shí)間都相等aj=bj=a(j=1,2,…,n)，且精確時(shí)間延遲是工序操作時(shí)間的整數(shù)倍lj=ka(k∈N+)。第一道工序在第一臺(tái)機(jī)器上執(zhí)行，第二道工序在第二臺(tái)機(jī)器上執(zhí)行，分別以極小化加權(quán)總完工時(shí)間，最大延誤時(shí)間和總延誤數(shù)為目標(biāo)函數(shù)，設(shè)計(jì)了最優(yōu)算法。

表1 帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)Tab.1 Flow operation of two machines with accurate time delay

上面問(wèn)題用三參數(shù)分別表示為：F2|exactlj,aj=bj=a,lj=ka|∑wjCj，F(xiàn)2|exactlj,aj=bj=a,lj=ka|Lmax，F(xiàn)2|exactlj,aj=bj=a,lj=ka|∑Uj這3個(gè)問(wèn)題。

2 F2|exact lj,aj=bj,lj=ka|∑wjCj的最優(yōu)算法

本節(jié)主要研究帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題。每個(gè)工件記為Jj(aj,bj,lj,wj)，目標(biāo)函數(shù)為極小化加權(quán)總完工時(shí)間。分別考慮以下3種情況：

2.1 F2|exact lj,aj=bj=lj=a|∑wjCj的最優(yōu)算法

當(dāng)aj=bj=lj=a時(shí)，sb1=2a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖∑wjCj。考慮單臺(tái)機(jī)排序問(wèn)題1‖∑wjCj，該問(wèn)題存在多項(xiàng)式時(shí)間最優(yōu)算法，Weighted Shortest Processing Time first (WSPT)，即

LWF (Longest Weighted first):將所有工件重新排序，使得w1≥w2≥…≥wn，再按照J(rèn)1,J2,…,Jn的順序加工工件。

定理2.1.1 LWF是問(wèn)題F2|exactlj,aj=bj=lj=a|∑wjCj的最優(yōu)算法，如圖1所示。

證明：用反證法。假設(shè)有一個(gè)最優(yōu)排序，比如σ*，違反了LWF規(guī)則，則σ*中一定存在相鄰的兩個(gè)工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(sbi+bi)+wk(sbi+bi+bk)-wi(sbi+bi+bk)-wk(sbi+bk)=wkpi-wipk>0

即所得的排序σ目標(biāo)值比最優(yōu)值還要小，矛盾！

注：當(dāng)wj=1時(shí)，問(wèn)題變?yōu)?|exactlj,aj=bj=lj=a|∑Cj

圖1 最優(yōu)排序Fig.1 Optimal sorting

2.2 F2|exact lj,aj=bj,lj=2a|∑wjCj的最優(yōu)算法

當(dāng)aj=bj=a,lj=2a時(shí)，sb1=3a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖∑wjCj。考慮單臺(tái)機(jī)排序問(wèn)題1‖∑wjCj，該問(wèn)題存在多項(xiàng)式時(shí)間最優(yōu)算法，Weighted Shortest Processing Time first (WSPT)，即

定理2.2.1 LWF是問(wèn)題F2|exactlj,aj=bj=lj=2a|∑wjCj的最優(yōu)算法，如圖2所示。

圖2 最優(yōu)排序Fig.2 Optimal sorting

證明：用反證法。假設(shè)有一個(gè)最優(yōu)排序，比如σ*，違反了LWF規(guī)則，則σ*中一定存在相鄰的兩個(gè)工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(sbi+bi)+wk(sbi+bi+bk)-wi(sbi+bi+bk)-wk(sbi+bk)=wkpi-wipk>0

即所得的排序σ目標(biāo)值比最優(yōu)值還要小，矛盾！

J1,J2,…,Jn的順序加工工件。

注：當(dāng)wj=1時(shí)，問(wèn)題變?yōu)?|exactlj,aj=bj=a,lj=2a|∑Cj

2.3 F2|exact lj,aj=bj,lj=ka|∑wjCj的最優(yōu)算法

定理2.3.1 LWF是問(wèn)題F2|exactlj,aj=bj,lj=ka|∑wjCj的最優(yōu)算法，如圖3所示。

圖3 最優(yōu)排序Fig.3 Optimal sorting

證明：用反證法。假設(shè)有一個(gè)最優(yōu)排序，比如σ*，違反了LWF規(guī)則，則σ*中一定存在相鄰的兩個(gè)工件Ji和Jk，使得wi

∑wjCj(σ*)-∑wjCj(σ)=wi(sbi+bi)+wk(sbi+bi+bk)-wi(sbi+bi+bk)-wk(sbi+bk)=wkpi-wipk>0

即所得的排序σ目標(biāo)值比最優(yōu)值還要小，矛盾！

J1,J2,…,Jn的順序加工工件。

注：當(dāng)wj=1時(shí)，問(wèn)題變?yōu)?|exactlj,aj=bj=a,lj=ka|∑Cj

3 F2|exact lj,aj=bj,lj=ka|Lmax的最優(yōu)算法

本節(jié)主要研究帶確切延誤的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題。每個(gè)工件記為Jj(aj,bj,lj,dj)，目標(biāo)函數(shù)為極小化最大延誤。分別考慮以下3種情況：

3.1 F2|exact lj,aj=bj=lj=a|Lmax的最優(yōu)算法

當(dāng)aj=bj=lj=a時(shí)，sb1=2a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖Lmax。單臺(tái)機(jī)最大延誤問(wèn)題1‖Lmax也可以找到多項(xiàng)式時(shí)間算法，Earliest Due Date first (EDD)，且是最優(yōu)算法。

EDD：將工件重新排序使得d1≤d2≤…≤dn，再按照J(rèn)1,J2,…,Jn順序加工。

定理3.1.1 EDD規(guī)則可以得到問(wèn)題F2|exactlj,aj=bj=lj=a|Lmax的最優(yōu)排序。

3.2 F2|exact lj,aj=bj,lj=2a|Lmax的最優(yōu)算法

當(dāng)aj=bj=a,lj=2a時(shí)，sb1=3a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖Lmax。單臺(tái)機(jī)最大延誤問(wèn)題1‖Lmax也可以找到多項(xiàng)式時(shí)間算法，Earliest Due Date first (EDD)，且是最優(yōu)算法。

定理3.2.1 EDD規(guī)則可以得到問(wèn)題F2|exactlj,aj=bj,lj=2a|Lmax的最優(yōu)排序。

3.3 F2|exact lj,aj=bj,lj=ka|Lmax的最優(yōu)算法

當(dāng)aj=bj=a,lj=ka時(shí)，sb1=(k+1)a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖Lmax。單臺(tái)機(jī)最大延誤問(wèn)題1‖Lmax也可以找到多項(xiàng)式時(shí)間算法，Earliest Due Date first (EDD)，且是最優(yōu)算法.

定理3.3.1 EDD規(guī)則可以得到問(wèn)題F2|exactlj,aj=bj,lj=ka|Lmax的最優(yōu)排序。

4 F2|exact lj,aj=bj,lj=ka|∑Uj的最優(yōu)算法

本節(jié)主要研究帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題，每個(gè)工件記為Jj(aj,bj,lj,dj)，目標(biāo)函數(shù)為極小化總延誤數(shù)。分別考慮以下3種情況：

4.1 F2|exact lj,aj=bj=lj=a|∑Uj的最優(yōu)算法

當(dāng)aj=bj=lj=a時(shí)，sb1=2a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖∑Uj。對(duì)于極小化誤工工件數(shù)的問(wèn)題1‖∑Uj，1968年Moore給出了一個(gè)多項(xiàng)式時(shí)間的最優(yōu)算法。

算法H:

①將工件按照EDD規(guī)則排序；

②計(jì)算當(dāng)前排序中各工件的完工時(shí)間，如果已無(wú)延誤，則轉(zhuǎn)④，否則轉(zhuǎn)③；

③找出第1個(gè)延誤的工件，比如是第i個(gè)工件，則將其刪除，得到一個(gè)部分排序，返回②；

④將刪除的工件以任意順序排到最后，所得部分排序之后，輸出所得排序。

定理4.1.1 算法H可以得到問(wèn)題F2|exactlj,aj=bj=lj=a|Lmax的最優(yōu)排序如圖4所示。

圖4 最優(yōu)排序Fig.4 Optimal sorting

證明：不妨d1≤d2≤…≤dn，設(shè)P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第③步中刪除的工件集合。不妨設(shè)F≠Φ，令工件k是算法第1次執(zhí)行到第③步時(shí)找到的延誤工件，于是i就是算法刪除的第1個(gè)工件。由算法規(guī)則可知 1,…,i-1沒(méi)有誤工工件，下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。

設(shè)P′=(S′,F′)是一個(gè)最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，不妨認(rèn)為dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得：

i∈{π(1),…,π(m)}?{1,…,i}，{π(m+1),…,π(r)}?{i+1,…,n}。

并且由i定義，序列1,…,i產(chǎn)生延誤，因而{π(1),…,π(m)}≠{1,…,i}。于是存在1≤h≤i，h?{π(1),…,π(m)}，所以有：

{π(1),…,π(m)}∪{h}{i}?{1,…,k}{i}。

由此可知：{π(1),…,π(m)}∪{h}{i}按照EDD排列后不產(chǎn)生延誤，且這些工件的總加工時(shí)間比{π(1),…,π(m)}中工件總加工時(shí)間減少了，這表明在上述工件序列之后加上原來(lái)的π(m+1),…,π(r)也不產(chǎn)生誤工工件。換句話說(shuō)，我們構(gòu)造出了一個(gè)誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

根據(jù)上面這個(gè)結(jié)論，對(duì)工件數(shù)目作歸納，證明定理結(jié)論：顯然，當(dāng)n=1時(shí)，該算法可以得到最優(yōu)排序。假設(shè)算法對(duì)工件數(shù)為n-1的實(shí)例均能找到最優(yōu)排序，則對(duì)任一工件數(shù)為n的實(shí)例，設(shè)P=(S,F)是算法所得的排序，工件i∈F如上定義。所以存在一個(gè)最優(yōu)排序P′=(S′,F′)，使得i∈F′，顯然有|S|≤|S′|。另一方面，考慮實(shí)例{1,…,i-1,i+1,…,n}，由歸納假設(shè)及算法規(guī)則，算法得到的排序形如P=(S,F{i})且是一個(gè)最優(yōu)排序。再注意到P′=(S′,F′{i})是該實(shí)例的可行排序，所以又可得到|S|≥|S′|。因此|S|=|S′|，算法對(duì)n個(gè)工件的實(shí)例也得到最優(yōu)排序。

4.2 F2|exact lj,aj=bj,lj=2a|∑Uj的最優(yōu)算法

當(dāng)aj=bj=a,lj=2a時(shí)，sb1=3a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖∑Uj。對(duì)于極小化誤工工件數(shù)的問(wèn)題1‖∑Uj，1968年Moore給出了一個(gè)多項(xiàng)式時(shí)間的最優(yōu)算法。

定理4.2.1 算法H可以得到問(wèn)題F2|exactlj,aj=bj,lj=2a|∑Uj的最優(yōu)排序如圖5所示。

圖5 最優(yōu)排序Fig.5 Optimal sorting

證明：不妨d1≤d2≤…≤dn，設(shè)P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第③步中刪除的工件集合。不妨設(shè)F≠Φ，令工件k是算法第1次執(zhí)行到第③步時(shí)找到的延誤工件，于是i就是算法刪除的第1個(gè)工件。由算法規(guī)則可知 1,…,i-1沒(méi)有誤工工件，下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。

設(shè)P′=(S′,F′)是一個(gè)最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，不妨認(rèn)為dπ(1)≤dπ(2)≤…≤dπ(r)。再由于d1≤d2≤…≤dn，所以一定存在m使得：

i∈{π(1),…,π(m)}?{1,…,i}，{π(m+1),…,π(r)}?{i+1,…,n}。并且由i定義，序列1,…,i產(chǎn)生延誤，因而{π(1),…,π(m)}≠{1,…,i}。于是存在1≤h≤i，h?{π(1),…,π(m)}，所以有：

{π(1),…,π(m)}∪{h}{i}?{1,…,k}{i}。

由此可知{π(1),…,π(m)}∪{h}{i}按照EDD排列后不產(chǎn)生延誤，且這些工件的總加工時(shí)間比{π(1),…,π(m)}中工件總加工時(shí)間減少了，這表明在上述工件序列之后加上原來(lái)的π(m+1),…,π(r)也不產(chǎn)生誤工工件。換句話說(shuō)，我們構(gòu)造出了一個(gè)誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

根據(jù)上面這個(gè)結(jié)論，對(duì)工件數(shù)目作歸納，證明定理結(jié)論：顯然當(dāng)n=1時(shí)，該算法可以得到最優(yōu)排序。假設(shè)算法對(duì)工件數(shù)為n-1的實(shí)例均能找到最優(yōu)排序，則對(duì)任一工件數(shù)為n的實(shí)例，設(shè)P=(S,F)是算法所得的排序，工件i∈F如上定義。所以存在一個(gè)最優(yōu)排序P′=(S′,F′)，使得i∈F′，顯然有|S|≤|S′|。另一方面，考慮實(shí)例{1,…,i-1,i+1,…,n}，由歸納假設(shè)及算法規(guī)則，算法得到的排序形如P=(S,F{i})且是一個(gè)最優(yōu)排序。再注意到P′=(S′,F′{i})是該實(shí)例的可行排序，所以又可得到|S|≥|S′|。因此|S|=|S′|，算法對(duì)n個(gè)工件的實(shí)例也得到最優(yōu)排序。

4.3 F2|exact lj,aj=bj,lj=ka|∑Uj的最優(yōu)算法

當(dāng)aj=bj=a,lj=ka時(shí)，sb1=(k+1)a。因?yàn)槊總€(gè)工件的第一道工序aj在第一臺(tái)機(jī)器上執(zhí)行，第二道工序bj在第二臺(tái)機(jī)器上執(zhí)行，并且它們之間存在的是精確時(shí)間延遲，所以當(dāng)?shù)诙拦ば騜j在第二臺(tái)機(jī)器上的開(kāi)始時(shí)間sbj確定時(shí)，對(duì)應(yīng)的第一道工序aj在第一臺(tái)機(jī)器的位置也唯一確定。因此只考慮每個(gè)工件的第二道工序bj，即此問(wèn)題等價(jià)于1‖∑Uj。對(duì)于極小化誤工工件數(shù)的問(wèn)題1‖∑Uj，1968年Moore給出了一個(gè)多項(xiàng)式時(shí)間的最優(yōu)算法。

定理4.3.1 算法H可以得到問(wèn)題F2|exactlj,aj=bj,lj=ka|∑Uj的最優(yōu)排序如圖6所示。

圖6 最優(yōu)排序Fig.6 Optimal sorting

證明：不妨d1≤d2≤…≤dn，設(shè)P=(S,F)為算法所得的排序，其中S為按期完工工件集，F(xiàn)為誤工工件集，即算法在第③步中刪除的工件集合。不妨設(shè)F≠Φ，令工件k是算法第1次執(zhí)行到第③步時(shí)找到的延誤工件，于是i就是算法刪除的第1個(gè)工件。由算法規(guī)則可知 1,…,i-1沒(méi)有誤工工件，下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。

設(shè)P′=(S′,F′)是一個(gè)最優(yōu)排序且i∈S′，并記F′=π(r+1)…π(n)，S′=π(1)…π(r)。不妨認(rèn)為dπ(1)≤dπ(2)≤…≤dπ(r)，再由于d1≤d2≤…≤dn，所以一定存在m使得：

i∈{π(1),…,π(m)}?{1,…,i}，{π(m+1),…,π(r)}?{i+1,…,n}。

并且由i定義，序列1,…,i產(chǎn)生延誤，因而{π(1),…,π(m)}≠{1,…,i}。于是存在1≤h≤i，h?{π(1),…,π(m)}，所以有：

{π(1),…,π(m)}∪{h}{i}?{1,…,k}{i}。

由此可知{π(1),…,π(m)}∪{h}{i}按照EDD排列后不產(chǎn)生延誤，且這些工件的總加工時(shí)間比{π(1),…,π(m)}中工件總加工時(shí)間減少了，這表明在上述工件序列之后加上原來(lái)的π(m+1),…,π(r)也不產(chǎn)生誤工工件。換句話說(shuō)，我們構(gòu)造出了一個(gè)誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

根據(jù)上面這個(gè)結(jié)論，對(duì)工件數(shù)目作歸納，證明定理結(jié)論：顯然當(dāng)n=1時(shí)，該算法可以得到最優(yōu)排序。假設(shè)算法對(duì)工件數(shù)為n-1的實(shí)例均能找到最優(yōu)排序，則對(duì)任一工件數(shù)為n的實(shí)例，設(shè)P=(S,F)是算法所得的排序，工件i∈F如上定義。所以存在一個(gè)最優(yōu)排序P′=(S′,F′)，使得i∈F′，顯然有|S|≤|S′|。另一方面，考慮實(shí)例{1,…,i-1,i+1,…,n}，由歸納假設(shè)及算法規(guī)則，算法得到的排序形如P=(S,F{i})且是一個(gè)最優(yōu)排序。再注意到P′=(S′,F′{i})是該實(shí)例的可行排序，所以又可得到|S|≥|S′|。因此|S|=|S′|，算法對(duì)n個(gè)工件的實(shí)例也得到最優(yōu)排序。

5 結(jié)語(yǔ)

主要研究了帶精確時(shí)間延遲的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題。第一道工序在第一臺(tái)機(jī)器上執(zhí)行，第二道工序在第二臺(tái)機(jī)器上執(zhí)行，分別以極小化加權(quán)總完工時(shí)間，最大延誤時(shí)間和總延誤數(shù)為目標(biāo)函數(shù)，設(shè)計(jì)了最優(yōu)算法。

需要進(jìn)一步研究和考慮的問(wèn)題還有：

①F2|exactlj|∑wjCj帶確切延誤的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題，目標(biāo)是加權(quán)總完工時(shí)間。

②F2|exactlj|Lmax帶確切延誤的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題，目標(biāo)是極小化最大延誤時(shí)間。

③F2|exactlj|∑Uj帶確切延誤的兩臺(tái)機(jī)流水作業(yè)排序問(wèn)題，目標(biāo)是總延誤數(shù)。