時凌，張瓊，時義梅，劉丁酉*

（1 廣州工商學(xué)院基礎(chǔ)教學(xué)部，廣東 廣州 510850；2 湖北民族民族學(xué)院理學(xué)院,湖北 恩施 445000;3 武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 湖北 武漢 430072）

帶運(yùn)輸時間和單自動機(jī)的流水作業(yè)排序問題可敘述為:假設(shè)給定由m臺機(jī)器構(gòu)成的機(jī)器集{M1,M2,...,Mm}和由n個工件組成的工件集{J1,J2,...,Jn}。每個工件Jj均有m道工序Qi,j(i=1,2,...,m;j=1,2,...,n),其加工順序Q1,j→Q2,j→...→Qm,j，其中，每道工序Qi,j在機(jī)器上Mi的加工時間為pi,j(pi,j≥0)。每臺機(jī)器在同一時間只能加工一個工件。

本文假設(shè)一個工件在一臺機(jī)器上完工后在下一臺機(jī)器加工之前存在一個時間間隔,即工序Qk,j在機(jī)器Mk上完工后,下一道工序Qk+1,j在機(jī)器Mk+1上加工之前需要一定的運(yùn)輸時間tj,k(tj,k≥0),所有的運(yùn)輸工作均由自動機(jī)R來完成，自動機(jī)同一時間也只能對一個工件進(jìn)行運(yùn)輸。這樣工件在運(yùn)輸和加工的過程中就可能會出現(xiàn)一定的沖突。

本文研究的目的是要確定可行排序使完工時間的加權(quán)和達(dá)到最小,即達(dá)到最小,其中Cj是工件Jj最后一道工序Qm,j的完工時間。依據(jù)Lawer E L等[1]提出的三元法,帶運(yùn)輸時間和單自動機(jī)的流水作業(yè)排序問題可表示為:,如果不帶運(yùn)輸時間和單自動機(jī)則可表示為。如果只考慮2臺機(jī)器,自動機(jī)只需在機(jī)器M1和機(jī)器M2之間運(yùn)輸,運(yùn)輸時間可簡化為tj,則該問題可表示為。本文主要研究當(dāng)所有加工時間均等于1,即時流水作業(yè)的排序,即研究排序的復(fù)雜性和啟發(fā)式算法。

現(xiàn)在考慮2臺加工機(jī)器M1、M2和單自動機(jī)R,n個工件在機(jī)器M1和機(jī)器M2上的加工時間分別為p1,j和自動機(jī)的運(yùn)輸時間為tj。

假設(shè)序列σ和τ分別表示工件在機(jī)器M1和機(jī)器上的加工順序,C(σ,τ)表示問題的最小完工時間。

引理1：考慮具有加工時間pi,j和運(yùn)輸時間

排序問題,則有:

引理1：證明過程與文獻(xiàn)[9]相似，本文省略。

定理1：問題是強(qiáng)NP-困難的。

證明：下面利用強(qiáng)NP-困難的3-劃分問題[10]到排序問題的歸約來證明F2,R1問題是強(qiáng)NP-困難的。

3-劃分問題可敘述為:給定正整數(shù)集X=和滿足條件(2)的正整數(shù)b

確定集合X是否可以分解為由3個不同元素組成的m個子集{X1,X2,...,Xm}且滿足:

給定3-劃分問題的一個實(shí)例,構(gòu)造F2,R1問題的實(shí)例:將n=mb+m+1個工件分解為三類:P-工件(劃分工件)記為;X-工件(輔助工件)記為;Z-工件(零工件)記為。運(yùn)輸時間和權(quán)重由如下公式給出:

(a)劃分工件。P-工件滿足:

(b)輔助工件。X-工件滿足，其中

(c)零工件。Z-工件滿足:其中

確定門檻值y=W(X)+W(P,Z),其中。相應(yīng)的確定性問題為:是否存在加工時間C(S)不超過y=W(X)+W(P,Z)的排序S?

圖1 子排序 SjFig.1 Subschedule Sj

圖2 最優(yōu)排序 S*Fig.2 Optimal schedu le S*

由P-工件得到的最優(yōu)排序S*和子排序Sj(j= 1,2,…,m)如圖2所示。

于是由圖1得到一個排序σ,顯然這個排序滿足wC(σ)≤y。相反假設(shè)流水作業(yè)排序問題存在滿足wC(σ)≤y的排序σ，在式(1)中令k=1,j=n,tj=0,則可得到一個滿足wC(σ)=y的排序σ，

W(X)+W(P,Z)=y，

從而得到了一個滿足wC(σ)=y的排序σ。由此可得：

(d)機(jī)器M1在區(qū)間[0,m(b+1)+1]上加工工件，無空閑;

(e)機(jī)器M2在區(qū)間[2,3+m(b+1)]上加工工件,無空閑;

(f)自動機(jī)R在區(qū)間[[1,2+m(b+1)]]上運(yùn)輸工件,無空閑。

不失一般性,假設(shè)工件按順序{1,2,...,m?1,m}加工工件,令X1={i1,i2,...,ik}表示工件X1和工件X2之間的工件集（圖3），有X1≠Φ，否則，在工件X1和工件X2中出現(xiàn)空閑，這與上面的(d)-(f)矛盾。

圖3 問題在 X1上的子排序Fig.3 Subscheduling for the

下面證明k=3和成立。

如果k≤2成立,則有:

于是自動機(jī)R完成工件X1的運(yùn)輸。這樣機(jī)器M2在工件X1和工件X2之間存在空閑時間，這與上面的(d)-(f)矛盾。

如果k≥4成立,則有:

另一方面,由于工件X1之前需要運(yùn)輸,工件X2不可能在時刻3+b之前在機(jī)器M2上進(jìn)行加工，于是工件X1在機(jī)器M2上的完工時間為,工件X2在機(jī)器M1上不可能完成集合X1中工件的加工,這與上面的(d)-(f)矛盾。

于是必須有k=3,且自動機(jī)R在區(qū)間[[2,2+(b+1)]]內(nèi)運(yùn)輸工件J1和工件J2,所以,即:

另外，由于機(jī)器M2在區(qū)間[4b,6b]內(nèi)不存在空閑時間,工件X1在機(jī)器M2上必須在時刻3b完工，因此，,又因?yàn)?w2,ik=b,所以有:

同理可證明余下的集合X2,X3,...,Xm也是由3個不相同元素組成且滿足的3-劃分問題的解。

2.1 啟發(fā)式算法1

步驟1：計(jì)算

步驟2：按單調(diào)不減的順序加工工件,即按以下順序加工工件:

2.2 最壞性能比

設(shè)Sj表示工件Jj的開工時間,I1,i表示工件Ji在機(jī)器上M1的總空閑時間，表示F2,R1問題的最優(yōu)排序。

定理2：對于問題,假設(shè)SH表示由啟發(fā)式算法1得到的近似解,則有:且上界是緊的。

同理可得:

實(shí)例1：假設(shè)自動機(jī)R的運(yùn)輸時間tj(j=1,2,3,4)和權(quán)重wj(j=1,2,3,4)如式（6）所示：

其加工順序如圖4和圖5所示。

圖4 最優(yōu)完工時間Fig.4 Optimal makespan

圖5 實(shí)例1的完工時間Fig.5 Example 1’makespan

定理2得證。

3 小結(jié)

(2)更一般的將流水作業(yè)排序問題推廣到自由作業(yè)排序問題,即排序問題時，待解決的問題是如何證明該問題的復(fù)雜性，以及如何構(gòu)造出相應(yīng)的啟發(fā)式算法以及對最壞性能比的討論等等。