帶單機器人的流水作業(yè)排序問題的復雜性

時 凌，張 瓊，龍彩燕

（廣州工商學院通識教育學院，廣東 廣州 510850）

0 引言

帶單機器人的流水作業(yè)排序問題可描述為：給定m臺機器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，且在加工時不可中斷.每臺機器在同一時間只能加工一個工件，而每個工件在同一時間只能在一臺機器上加工.筆者假設(shè)同一工件在一臺機器上完工后到下一臺機器加工之前存在一定的運輸時間tj,k，所有的運輸工作均由單機器人R來完成，且單機器人R同時只能運輸一個工件，于是在機器人R和機器Mi之間就會出現(xiàn)一定的沖突.假設(shè)所有的加工時間pi,j和運輸時間tj,k均為正整數(shù).

1 排序問題F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmax 的復雜性

由于排序問題F3||C存在同順序最優(yōu)解［8］，所以該排序問題只考慮同順序的最優(yōu)解.用σ和τ分別表示工件在機器M1和M2上的加工順序，C(σ,τ)表示排序問題的最小完工時間.

引理1［2］對于加工時間和運輸時間分別為pi,j、tj的排序問題則：

其中，σ-1(k)和τ-1(k)分別表示工件Jk在序列σ和τ中的相應(yīng)位置.

定理1排序問題是強NP-困難的.

證明利用強NP-困難的3-劃分問題［9］到排序問題的歸約來證明該排序問題也是強NP-困難的.

3-劃分問題：給定正整數(shù)集X={x1,x2,...,x3m}和正整數(shù)b，且滿足

確定整數(shù)集X是否存在包含3個元素的m個不相交的子集{X1,X2,...,Xm}的劃分，且

給定3-劃分問題的一個實例，定義具有下面2類工件的排序問題

（1）3m劃分工件，或者稱為P-工件：

（2）m大工件，或者稱為L-工件：

門檻值為y=3mb+3b，相應(yīng)的確定性問題為：是否存在完工時間C(S)不超過門檻值y=3mb+3b的加工順序S.

假設(shè)3-劃分問題的解存在，設(shè) {X1,X2,...,Xm}是滿足式（3）的劃分，其中，Xi=(xξ(i),xη(i),x?(i))(i=1,2,...,m).

對于每個工件Jj構(gòu)建包含工件ξ(j),η(j),?(j)和工件 3m+j，其加工順序為 ((3m+1);ξ(1),η(1),?(1);(3m+2);ξ(2),η(2),?(2);...;(4m-1);ξ(m),η(m),?(m);4m)，如圖1 所示.

圖1 排序問題F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmax的甘特圖Fig.1 Gantt chart for the F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmaxscheduling problem

則對于圖1給出的加工順序S，顯然滿足：C(S)≤y.

于是得到同順序的S且C(S)=y，且有如下結(jié)論：

（1）因為p1,j＞0，先加工工件(3m+1)；

（2）因為p2,j＞0（j≠m），工件4m安排在最后加工；

（3）機器M1在區(qū)間［0,3mb］內(nèi)加工工件，且無空閑時間；

（4）機器M2在區(qū)間［3b,3mb+3b］內(nèi)加工工件，且無空閑時間；

（5）單機器人R在區(qū)間[(3i+2)b,(3i+4)b](i=0,1,...,(m-1))內(nèi)運輸工件，且無空閑時間.

不失一般性，假設(shè)機器以{1,2,...,m-1,m}的順序加工工件，即按單調(diào)遞增的順序加工工件.設(shè)工件(3m+1)與工件(3m+2)之間加工的工件子集為X1={i1,i2,...,ik}，如圖2所示.

圖2 排序問題F2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmax的子圖Fig.2 Subgraph for theF2,R1| p1,j=p2,j=pj;tj∈{T1,T2}|Cmaxscheduling problem

于是X1≠Φ，否則在工件(3m+1)和工件(3m+2)出現(xiàn)空閑時間，與結(jié)論（3）～（5）矛盾.下面證明k=3和成立.假設(shè)表示工件Jj按加工順序σ在機器Mi上的完工時間，則：

如果k≤2，則有：

如果k≥4，則有：

另一方面，由于工件(3m+1)必須先完成運輸才能加工，因此工件(3m+2)不會在時間2b+kb之前在機器M加工.于是工件(3m+1)在機器M完工時間為，但工件(3m+2)在機器M1上還沒有完成集合X1中工件的加工，與結(jié)論（4）矛盾，故必須有k=3.這就意味著單機器人R在時間段[2b,3b]和時間段[3b,4b]運輸工件 (3m+1)和工件 (3m+2).所以，即：

另外，由于機器M2在時間段[4b,6b]沒有空閑時間，因此工件(3m+1)在機器M2上的完工時間不遲于6b，則有：

因為p1,i=p2,i=xi，所以

即X1是包含3個元素且滿足

同理可證余下的集合X2,X3,...,Xm也是滿足包含3個元素且滿足故集合X1,X2,...,Xm就是包含3元素且滿足的3-劃分問題的解.

證畢.

2 小結(jié)