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

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

帶運輸時間和單自動機的流水作業(yè)排序問題可敘述為:假設(shè)給定由m臺機器構(gòu)成的機器集{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在機器上Mi的加工時間為pi,j(pi,j≥0)。每臺機器在同一時間只能加工一個工件。

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

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

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

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

引理1：考慮具有加工時間pi,j和運輸時間

排序問題,則有:

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

定理1：問題是強NP-困難的。

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

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

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

給定3-劃分問題的一個實例,構(gòu)造F2,R1問題的實例:將n=mb+m+1個工件分解為三類:P-工件(劃分工件)記為;X-工件(輔助工件)記為;Z-工件(零工件)記為。運輸時間和權(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)機器M1在區(qū)間[0,m(b+1)+1]上加工工件，無空閑;

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

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

不失一般性,假設(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成立,則有:

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

如果k≥4成立,則有:

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

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

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

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

2.1 啟發(fā)式算法1

步驟1：計算

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

2.2 最壞性能比

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

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

同理可得:

實例1：假設(shè)自動機R的運輸時間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 實例1的完工時間Fig.5 Example 1’makespan

定理2得證。

3 小結(jié)

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