帶精確時間延遲的兩臺機流水作業(yè)問題研究

王煥男

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

1 引言

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

對上述研究綜述進行匯總?cè)绫?所示。

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

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

上面問題用三參數(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個問題。

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

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

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

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

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

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

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

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

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

注：當wj=1時，問題變?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)算法

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

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

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

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

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

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

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

注：當wj=1時，問題變?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是問題F2|exactlj,aj=bj,lj=ka|∑wjCj的最優(yōu)算法，如圖3所示。

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

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

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

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

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

注：當wj=1時，問題變?yōu)?|exactlj,aj=bj=a,lj=ka|∑Cj

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

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

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

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

EDD：將工件重新排序使得d1≤d2≤…≤dn，再按照J1,J2,…,Jn順序加工。

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

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

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

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

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

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

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

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

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

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

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

算法H:

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

②計算當前排序中各工件的完工時間，如果已無延誤，則轉(zhuǎn)④，否則轉(zhuǎn)③；

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

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

定理4.1.1 算法H可以得到問題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í)行到第③步時找到的延誤工件，于是i就是算法刪除的第1個工件。由算法規(guī)則可知 1,…,i-1沒有誤工工件，下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。

設(shè)P′=(S′,F′)是一個最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，不妨認為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)生延誤，且這些工件的總加工時間比{π(1),…,π(m)}中工件總加工時間減少了，這表明在上述工件序列之后加上原來的π(m+1),…,π(r)也不產(chǎn)生誤工工件。換句話說，我們構(gòu)造出了一個誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

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

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

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

定理4.2.1 算法H可以得到問題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í)行到第③步時找到的延誤工件，于是i就是算法刪除的第1個工件。由算法規(guī)則可知 1,…,i-1沒有誤工工件，下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。

設(shè)P′=(S′,F′)是一個最優(yōu)排序且i∈S′。并記F′=π(r+1)…π(n)，S′=π(1)…π(r)，不妨認為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)生延誤，且這些工件的總加工時間比{π(1),…,π(m)}中工件總加工時間減少了，這表明在上述工件序列之后加上原來的π(m+1),…,π(r)也不產(chǎn)生誤工工件。換句話說，我們構(gòu)造出了一個誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

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

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

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

定理4.3.1 算法H可以得到問題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í)行到第③步時找到的延誤工件，于是i就是算法刪除的第1個工件。由算法規(guī)則可知 1,…,i-1沒有誤工工件，下面首先證明：存在最優(yōu)排序P′=(S′,F′)(S′和F′定義同上)，使得i∈F′。

設(shè)P′=(S′,F′)是一個最優(yōu)排序且i∈S′，并記F′=π(r+1)…π(n)，S′=π(1)…π(r)。不妨認為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)生延誤，且這些工件的總加工時間比{π(1),…,π(m)}中工件總加工時間減少了，這表明在上述工件序列之后加上原來的π(m+1),…,π(r)也不產(chǎn)生誤工工件。換句話說，我們構(gòu)造出了一個誤工工件數(shù)與P′相同但i是誤工工件的排序，即得到了滿足要求的最優(yōu)排序。

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

5 結(jié)語

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

需要進一步研究和考慮的問題還有：

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

②F2|exactlj|Lmax帶確切延誤的兩臺機流水作業(yè)排序問題，目標是極小化最大延誤時間。

③F2|exactlj|∑Uj帶確切延誤的兩臺機流水作業(yè)排序問題，目標是總延誤數(shù)。