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

時凌， 張瓊， 龍彩燕

(廣州工商學院 通識教育學院, 廣東 廣州 510850)

0 引言

假設Ci,j為工件Jj在機器Mi上的完工時間.若在機器M1和機器M2上不存在空閑時間,則有:

C1,1=s1,1+p1,1,C2,1=s1,1+p1,1+s2,1+p2,1,

C1,j=C1,j -1+s1,j+p1,j,C2,j=max{C2,j -1,C1,j}+s2,j+p2,j, 其中j=2,…,n.

為了證明定理1,構(gòu)造由下面7n個工件組成的工件組：

1)P-工件:s1,i=b,p1,i=b;s2,i=b+xi,p2,i=b(i=1,2,…,n).

2)Q-工件:s1,i=0,p1,i=b;s2,i=b+yi,p2,i=b(i=1,2,…,n).

3)R-工件:s1,i=0,p1,i=b;s2,i=b-zi,p2,i=b(i=1,2,…,n).

4)U-工件:s1,i=0,p1,i=b;s2,i=0,p2,i=b(i=1,2,…,n).

5)V-工件:s1,i=0,p1,i=b;s2,i=0,p2,i=b(i=1,2,…,n).

6)W-工件:s1,i=0,p1,i=b;s2,i=0,p2,i=b(i=1,2,…,n).

7)L-工件:s1,i=4b,p1,i=b;s2,i=b,p2,i=b(i=1,2,…,n).

假設數(shù)字匹配問題有解,機器在加工過程中無空閑時間，其中機器M1按工序σ(σ={σP1,1,σQ1,1,σR1,1,σU1,1,σV1,1,σW1,1,σL1,1,…,σP1,n,σQ1,n,σR1,n,σU1,n,σV1,n,σW1,n,σL1,n})加工工件，機器M2按工序τ(τ={τP2,1,τQ2,1,τR2,1,τU2,1,τV2,1,τW2,1,τL2,1,…,τP2,n,τQ2,n,τR2,n,τU2,n,τV2,n,τW2,n,τL2,n})加工工件，如圖1所示.

圖排序問題的甘特圖

C(S)≥3b+x1+5b+x1+y1+7b+x1+y1-z1+8b+9b+10b+…+

(3+(n-1)11)b+x++(5+(n-1)11)b+xn+yn+(7+(n-1)11)b+…+

且使得C(S)=y.

由以上可知：如果加工順序S存在這樣的分解μ， 則完工時間等于y的加工順序(如圖1所示)；如果加工順序S不存在這樣的分解μ， 即加工順序S不是數(shù)字匹配問題的解,則xi+yi≠zi(i=1,2,…,n).令ξi=xi+yi-zi(i=1,2,…,n), 則ξi>0或者ξi<0 (對于ξi<0同理討論).由上述可得：

該式與C(S)=y矛盾，證畢.

證明對于加工順序S, 記Ii,j(S) (i=1,2;j=1,…,n)為工件Jj在機器Mi上的總空閑時間.如果在機器M1上的加工路徑為1,…,j, 在機器M2上加工的工件為Jj, 則有:

(1)

如果在機器M1上的加工工件為J1, 在機器M2上的加工順序為1,2,…,j, 則有:

(2)

如果在機器M1上的加工順序為1,…,l, 在機器M2上的加工順序為l,…,j, 則有:

(3)

由式(1)—式(3)有:

為了證明上界的緊性,本文構(gòu)造了如下2種工件：

1)P-工件:s1,i=2b,p1,i=b,s2,i=2b,p2,i=b(i=1,2);

2)Q-工件:s1,i=0,p1,i=b,s2,i=0,p2,i=b(i=3,4).

圖2 忙加工順序S0的總完工時間 圖3 最優(yōu)加工順序S*的總完工時間

3 結(jié)語