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

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

0 引 言

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

性質(zhì)1單位工件、有序約束的三臺機(jī)流水作業(yè)最優(yōu)排序?yàn)椋菏沟妹總€工件的三道工序可以進(jìn)行無等待加工，即對任意工件Jj，有si+1,j=sij+1。

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

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

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

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

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

圖1 LCG的自然分層

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 算法的緊例

3 結(jié)束語

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