一類帶特殊序約束的三臺機流水作業(yè)排序問題

陳占文，張 安，陳 永，陳光亭

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.臺州學(xué)院電子與信息工程學(xué)院，浙江 臺州 318000)

0 引 言

帶有特定順序約束的排序問題在實際中有著極為廣泛的應(yīng)用，但是，由于其復(fù)雜性大多是NP-難的，因此，很多問題尚未解決。給定m臺流水作業(yè)機器M1,M2,…,Mm，每個工件必須依次在M1,M2,…,Mm上不重疊地加工一個單位時間，稱為工件的m道工序。對任意2個工件Jj,Jk，若其有序約束為JjJk，則工件Jk的第一道工序必須在工件Jj的第m道工序完工后才能加工。工件之間的這種序約束關(guān)系可以用有向無圈圖(Directed Acyclic Graph，DAG)來刻畫，稱為序約束圖。沒有序約束的流水作業(yè)排序可視為序約束圖為空圖的特殊情形，其中三臺機流水作業(yè)排序問題是強NP-難的[1]，從而有序約束的對應(yīng)問題F3|prec|Cmax也是強NP-難的。當(dāng)考慮單位工件時，常數(shù)臺(m≥3)機器流水作業(yè)排序問題Fm|prec,pij=1|Cmax的計算復(fù)雜性仍是一個尚未解決的公開難題[2](兩臺機情形是多項式時間可解的[3])。當(dāng)機器臺數(shù)作為輸入時，F(xiàn)|prec,pij=1|Cmax問題是強NP-難的[4]。如果序約束圖具有某些特殊結(jié)構(gòu)，比如當(dāng)序約束圖為樹時，即使機器臺數(shù)作為輸入，流水作業(yè)排序問題F|tree,pij=1|Cmax也是多項式時間可解的[3]。文獻[5]在研究有序約束的開放作業(yè)排序問題時引入了一類新型序約束圖，該圖中所有頂點(即工件)均包含于某條最長鏈上，它是不同于樹的特殊序約束結(jié)構(gòu)，本文稱之為最長鏈圖(Longest Chains Graph，LCG)。LCG的發(fā)現(xiàn)對設(shè)計開放作業(yè)排序問題的近似算法起到重要作用。本文研究單位工件、有LCG型序約束的三臺機流水作業(yè)排序問題F3|LCG,pij=1|Cmax，設(shè)計了一個最壞情況界是3/2的近似算法。

1 最優(yōu)排序結(jié)構(gòu)與最優(yōu)值估計

令圖G=(J,A)為給定的LCG，其中J={J1,J2,…,Jn}為頂點集，A為有向邊集。若(Jj,Jk)∈A，則表示工件Jj,Jk之間有序約束關(guān)系JjJk。假設(shè)工件Jj在機器Mi上的開工時間為sij。對于單位工件、有序約束的三臺流水作業(yè)排序問題，其最優(yōu)排序具有以下性質(zhì)。

性質(zhì)1單位工件、有序約束的三臺機流水作業(yè)最優(yōu)排序為：使得每個工件的三道工序可以進行無等待加工，即對任意工件Jj，有si+1,j=sij+1。

證明用數(shù)學(xué)歸納法證明。假設(shè)工件在機器M1上的加工順序為J1,J2,…,Jn，機器M1上可以存在空閑，機器M1的開工時刻為0時刻。

首先證明工件J1滿足性質(zhì)1。s11=0時，假設(shè)最優(yōu)排序中工件J1在機器M2上的開工時間s21≠1，此時，機器M2上的1至2時刻無工件加工。同時考慮機器M1上1至2時刻的工件加工情況，當(dāng)M1上1至2時刻為空閑時，工件J1在機器M2上的1時刻開工不會與M1上加工的工件沖突；當(dāng)機器M1上1至2時刻加工的工件為J2時，工件J1與J2無序約束關(guān)系；同樣，工件J1可以在機器M2上的1時刻開工，與假設(shè)s21≠1矛盾，即最優(yōu)排序s21=1。同理可證s31=2。所以，工件J1可以進行無等待加工。

假設(shè)前k個工件J1,J2,…,Jk滿足性質(zhì)1，下面證明工件Jk+1滿足性質(zhì)1。設(shè)工件Jk+1在機器M1上的開工時刻為k+1，且最優(yōu)排序有s2,k+1≠k+2，則機器M2上k+2至k+3時刻無工件加工。同理可得機器M1上的k+2至k+3時刻無工件加工或者加工的工件為Jk+2時，都有工件Jk+1可以在機器M2上的時刻k+2開工。與假設(shè)s2，k+1≠k+2矛盾，所以最優(yōu)排序s2，k+1=k+2。同理可證s3,k+1=k+3。所以，工件Jk+1可以進行無等待加工。

綜上所述，當(dāng)機器M1加工工件順序為J1,J2,…,Jn時，由si+1,j=sij+1且s11=0，可知機器M2和M3的開工時刻分別為1時刻和2時刻，并且機器M2和M3按照相同的順序加工工件，因此，當(dāng)機器M1上加工的工件Ji前存在空閑時，機器M2和M3上工件Ji之前存在同樣的空閑，結(jié)論成立。證畢。

在算法設(shè)計和分析之前，首先需要對LCG進行自然分層。具體步驟為：將所有當(dāng)前可加工的工件(序約束圖入度為0的頂點)分為一層，刪去已分層的工件并更新LCG，對剩余的子圖重復(fù)操作，直至所有工件分層完畢。如果工件滿足J1J3，J3J2時，仍有J1J2，稱有向邊(J1,J2)為多余邊，分層完成后，將LCG中的多余邊刪除。假設(shè)自然分層將LCG分為l層，每一層構(gòu)成一個工件集合，得到工件集的劃分：D1,D2,…,Dl。自然分層的實例如圖1所示，將LCG共分為l層，每一層的工件用虛線圈出，多余邊為虛線所示的有向邊。

圖1 LCG的自然分層

2 近似算法設(shè)計與最壞情況分析

任一頂點集Di中的工件相互之間無序約束關(guān)系，因此按D1,D2,…,Dl順序最優(yōu)安排各頂點集中的工件并在相鄰頂點集之間空閑2個單位時間，所得排序一定為可行排序，但相應(yīng)的最大工件完工時間Cmax較大。

本文提出的改進算法就是在保證算法解可行的情況下，將相鄰頂點集之間的空隙縮減至1個單位時間。為此，需要為相鄰頂點集盡可能尋找一組相容的工件對，作為相鄰頂點集的鄰接工件，相容的定義如下：

定義1假設(shè)工件Jα∈Di，工件Jβ∈Di+1，當(dāng)工件Jα與Jβ之間無序約束關(guān)系時，工件對Jα與Jβ稱為相鄰頂點集Di與Di+1的相容工件對。工件Jα與工件Jβ的關(guān)系稱為相容。

問題F3|LCG,pij=1|Cmax的近似算法具體步驟如下。

輸入：一個LCGG=(V,E)

輸出：圖G中頂點(工件)的一個可行排序

(1)將LCG自然分層，得到各層頂點集D1,D2,…,Dl；

(2)尋找Di與Di+1(i=1,2,…,l-1)的相容工件對(同一工件至多與一個頂點集的某工件組成相容工件對)；

(3)按D1,D2,…,Dl順序最優(yōu)安排頂點集的工件，如果相鄰頂點集找到相容工件對，則將相容工件對作為兩頂點集的鄰接工件，并在相鄰頂點集之間空閑1個單位時間。否則相鄰頂點集之間空閑2個單位時間。

下面分析算法的最壞情況界。

算法在頂點集Di與Di+1之間無法找到相容工件對時，算法在頂點集Di的全部工件加工完畢后空閑2個單位時間。此時頂點集Di與下層頂點集Di+1的結(jié)構(gòu)有以下兩種情況：

情況2頂點集Di與下層頂點集Di+1之間不為完全二部圖。假設(shè)滿足條件的頂點集共有k個，則有如下定理：

定理2算法的最壞情況界至多為3/2，且是緊的。

根據(jù)定理1的結(jié)論，可得：

圖2 算法的緊例

3 結(jié)束語

針對單位工件、有最長鏈圖型序約束的三臺機流水作業(yè)排序問題，本文通過對序約束圖自然分層并為相鄰頂點集尋找相容工件對的方法設(shè)計了多項式時間近似算法，證明了算法的最壞情況界為3/2，同時給出緊例。由于算法僅通過相鄰頂點集的結(jié)構(gòu)來確定相容工件對，存在尋找相容工件對效率不高的問題，后續(xù)將改進尋找方法，得到更好的下界。