張先超，周 泓

1.東南大學(xué) 信息科學(xué)與工程學(xué)院，南京 210096

2.北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100191

生產(chǎn)調(diào)度是將有限的資源，如設(shè)備、場地、人員等，按時間分配給任務(wù)，使得一個或幾個目標(biāo)值達(dá)到最優(yōu)。由此可見，生產(chǎn)調(diào)度涉及到任務(wù)、資源和任務(wù)在資源上的處理時間等眾多因素。然而，實際生產(chǎn)過程中的很多因素是不確定的，經(jīng)常導(dǎo)致無法按照既定的初始調(diào)度方案實施生產(chǎn)，在生產(chǎn)過程中需要對初始調(diào)度方案進(jìn)行一定的調(diào)整，這對生產(chǎn)過程和生產(chǎn)結(jié)果都會產(chǎn)生一定的影響。在這種情況下，為了順利完成生產(chǎn)，確保生產(chǎn)結(jié)果，要求初始調(diào)度方案在一定限度的不確定因素擾動下，小幅調(diào)整即可實施，并能實現(xiàn)滿意的結(jié)果。將初始調(diào)度具有的這樣的性質(zhì)稱為魯棒性，具有魯棒性的初始調(diào)度方案稱為魯棒性初始調(diào)度方案?？梢允褂迷诓淮_定因素擾動下，實際調(diào)度目標(biāo)與能夠達(dá)到的最優(yōu)調(diào)度目標(biāo)的差距作為調(diào)度魯棒性的指標(biāo)，用以度量初始調(diào)度方案的魯棒性[1]。

在離散制造業(yè)中，流水車間（flow shop）是一種典型的作業(yè)模式，在生產(chǎn)制造的整個過程或關(guān)鍵部分環(huán)節(jié)被廣泛運(yùn)用。兩臺機(jī)器串行構(gòu)成的兩階段流水線是最為簡單的流水車間結(jié)構(gòu)，其調(diào)度問題的研究，在理論上是其他更為復(fù)雜的流水車間調(diào)度問題研究的基礎(chǔ)，在實際生產(chǎn)中也有著廣泛的應(yīng)用，例如，汽車的某些沖壓件需要依次經(jīng)過整形和沖孔兩道工序。

加工時間不確定是制造過程中一種常見的影響調(diào)度方案實施的不確定因素，以往很多學(xué)者將不確定的加工時間作為隨機(jī)變量，求解期望調(diào)度目標(biāo)最優(yōu)的調(diào)度方案，稱這樣的調(diào)度問題為隨機(jī)調(diào)度，可以使用隨機(jī)優(yōu)化等多種方法予以解決[2-3]。然而，在很多情況下，加工時間未必服從某一確切的概率分布函數(shù)，即便如此，也難以獲得準(zhǔn)確的概率分布，此外，非常滿意的隨機(jī)調(diào)度方案在一次具體的生產(chǎn)過程中也可能導(dǎo)致較差的生產(chǎn)結(jié)果。因此，在加工時間不確定的環(huán)境下，隨機(jī)調(diào)度具有很大的局限性。相比隨機(jī)調(diào)度，魯棒調(diào)度不要求加工時間的準(zhǔn)確的分布函數(shù)，而且，求取的調(diào)度方案在任何可能的加工時間情景下都能獲得比較滿意的生產(chǎn)效果。

近年來，對于加工時間不確定的魯棒調(diào)度問題，已經(jīng)有了一定的研究。文獻(xiàn)[4]給出了流水車間調(diào)度算法的魯棒性。文獻(xiàn)[5]研究了加工時間是離散情景，分布式流水生產(chǎn)魯棒調(diào)度問題的局部搜索算法。文獻(xiàn)[6]研究了加工時間不確定的job-shop魯棒調(diào)度問題，也是將加工時間描述為離散情景，運(yùn)用鄰域搜索，結(jié)合模擬退火和鄰域搜索求解。加工時間為離散情景在實際生產(chǎn)中并不常見，用區(qū)間數(shù)來表征實際生產(chǎn)中的加工時間更具有適用性。Liao等[7]研究了加工時間為區(qū)間數(shù)的置換流水車間Min-Max準(zhǔn)則魯棒調(diào)度問題，并運(yùn)用遺傳算法求解該問題。Levorato 等[8]研究了加工時間是區(qū)間分布，以工期為調(diào)度目標(biāo)的魯棒調(diào)度問題，建立混合整數(shù)規(guī)劃模型，使用列和約束生成算法求解。Wu等[9]也是針對以工期為目標(biāo)的兩階段流水車間，研究了加工時間依賴具體情境的Min-Max魯棒調(diào)度問題。相比工期，總完工時間在實際生產(chǎn)中有著更廣泛的意義，例如，總完工時間與庫存密切相關(guān)，減小總完工時間可以降低庫存，提高資金周轉(zhuǎn)率。進(jìn)一步來看，使用總完工時間作為調(diào)度目標(biāo)，對于生產(chǎn)以外的其他領(lǐng)域也同樣具有很好的適用價值。文獻(xiàn)[10]研究了針對云資源，以總完工時間為目標(biāo)的調(diào)度問題。Sun等[11]研究了以總完工時間及其偏差的和為目標(biāo)的流水車間魯棒調(diào)度問題，但其加工時間表征為離散情景。

流水車間魯棒調(diào)度問題的求解往往具有很高的復(fù)雜性，降低計算復(fù)雜性也是研究的重點(diǎn)。Cwik等[12]針對加工時間為區(qū)間數(shù)的，以工期為調(diào)度目標(biāo)的流水車間魯棒調(diào)度問題，通過兩次松弛來降低計算復(fù)雜度。利用調(diào)度解的占優(yōu)特點(diǎn)（dominance）是降低復(fù)雜性的常用手段。在不確定加工時間的環(huán)境下，很少存在對于任何加工時間情景都是最優(yōu)的調(diào)度解，但可能會存在任意加工時間情景下，某些調(diào)度解都會優(yōu)于另外的一些調(diào)度解，稱這樣的調(diào)度解是占優(yōu)的。Allahverdi和Sotskov[13]證明了加工時間是隨機(jī)數(shù)或區(qū)間數(shù)的兩臺機(jī)器流水車間魯棒調(diào)度占優(yōu)解的充分條件。Matsveichuk和Sotskov等[14]求解了該魯棒調(diào)度問題的占優(yōu)解集，對于某一特定的加工時間情景，占優(yōu)解集至少包含這種加工時間情景下的一個最優(yōu)調(diào)度解。Wu等[15]針對以總完工時間為目標(biāo)的兩階段流水車間調(diào)度問題，給出了利用占優(yōu)條件的分支定界算法，以及CA、GSA 等啟發(fā)式算法。然而，占優(yōu)解集在實際應(yīng)用中有著很大的局限性，需要根據(jù)當(dāng)前的生產(chǎn)情況實時選擇調(diào)度方案，需要高效率的算法支持，且對實現(xiàn)的調(diào)度目標(biāo)沒有準(zhǔn)確的預(yù)期。

本文研究以總完工時間作為調(diào)度目標(biāo)，加工時間為區(qū)間數(shù)的兩階段流水生產(chǎn)魯棒調(diào)度問題，使得在所有可能的加工時間情景下，調(diào)度目標(biāo)相對相應(yīng)的最優(yōu)調(diào)度目標(biāo)的最大偏差最小，即求解Min-Max準(zhǔn)則的魯棒調(diào)度解。

1 問題描述與模型

1.1 魯棒調(diào)度的三元組形式

1.2 魯棒調(diào)度的三元組形式

由此，調(diào)度在所有加工時間情景下調(diào)度目標(biāo)相對最優(yōu)調(diào)度目標(biāo)的最大偏差為：

設(shè)調(diào)度σR滿足：

則調(diào)度σR為調(diào)度目標(biāo)最大偏差最小的調(diào)度方案，即Min-Max準(zhǔn)則的魯棒調(diào)度方案。

1.3 數(shù)學(xué)模型

為建立問題的數(shù)學(xué)規(guī)劃模型，引入變量xjk和，規(guī)定如下：

式（4）給出了xjk(j,k=1,2,…,n)與調(diào)度σ的一一對應(yīng)關(guān)系。那么，在加工時間情景λ下，調(diào)度σ的第j個位置的工件σ(j)在兩臺機(jī)器上的加工時間為：

同理，根據(jù)式（5），得到：

根據(jù)式（7）和（8），在加工時間情景λ下，調(diào)度σ和最優(yōu)調(diào)度σλ中第j個位置的工件σ(j)和σλ(j)的完工時間分別為：

那么，調(diào)度σ和σλ的總完工時間為：

根據(jù)式（11）和（12），得到：

由此，式（3）轉(zhuǎn)換為以下的整數(shù)規(guī)劃模型：

在模型（14）中，約束（a）使得每個工件在調(diào)度σ中位于且僅位于一個位置，約束（b）是調(diào)度σ中每個位置有且僅有一個工件，約束（c）是式（6）對的求解，約束（d）表明xtk是0-1變量。

進(jìn)一步，式（14）改寫為：

模型（15）中約束（b）到（e）同模型中約束（a）到（d），求解的τ即為最小最大調(diào)度目標(biāo)偏差。根據(jù)模型（15）的解{xtk|t,k=1,2,…,n} 形成的調(diào)度方案即為Min-Max準(zhǔn)則的魯棒調(diào)度σR。由于區(qū)間數(shù)加工時間的情景集合Λ是無窮集合，那么，模型（15）具有無窮約束，是半無限規(guī)劃模型。

2 簡化性質(zhì)與占優(yōu)性質(zhì)

根據(jù)式（18），對式（13）進(jìn)行變換，得到：

根據(jù)式（19），式（2）給出的區(qū)間數(shù)加工時間環(huán)境下，調(diào)度σ的總完工時間最大偏差的求解如式（20）所示：

定理1（簡化性質(zhì)）對于給定的調(diào)度σ，使得總完工時間偏差最大的情景一定是工件加工時間取其所在時間區(qū)間的極端值。

定理1 將區(qū)間數(shù)工件時間轉(zhuǎn)化為可列可數(shù)加工時間情景，使得模型（20）的約束個數(shù)有限化，模型得以簡化，便于問題的求解。

設(shè)b是B中的任意一個工件，b∈B，那么

設(shè)c是C中的任意一個工件，c∈C，容易得到：

根據(jù)式（22）、（24）、（26）和（27），得到：

定理2成立。

定理3（占優(yōu)性質(zhì)）對于已經(jīng)給出調(diào)度方案的工件集合σs，以及尚未調(diào)度的工件i和j，如果滿足以下條件：

則存在工件j不是工件集合σs的緊后工件的魯棒調(diào)度方案。

設(shè)調(diào)度σ={σsiAjB}，對于滿足給定條件的任意加工時間情景，都有：

又根據(jù)式（30）的給定條件，得到：

根據(jù)式（31），易得：

根據(jù)式（32）和（33），得到：

顯然

那么，根據(jù)式（29），得到：

又因為

根據(jù)式（35）、（36）和（37），得到：

根據(jù)式（32）、（34）、（36）和（38），得到：

定理3成立。

定理2 和定理3 給出了所求調(diào)度的占優(yōu)條件，用以縮小解空間，可以減小分支定界方法搜索的節(jié)點(diǎn)數(shù)目，從而降低求解難度。

3 分支定界-遺傳算法

在加工時間為區(qū)間數(shù)的環(huán)境下，Min-Max準(zhǔn)則魯棒調(diào)度解的搜索涉及到調(diào)度解和加工時間兩個空間。先對于給定的調(diào)度解，搜索總完工時間偏差最大的加工時間情景，再從調(diào)度解空間中搜索最大偏差最小的調(diào)度解，即魯棒調(diào)度解。遺傳算法具有很好的全局搜索性，具有廣泛的適用性[17-18]。本文將分支定界方法與遺傳算法結(jié)合起來，設(shè)計分支定界-遺傳混合算法（branch and bound-genetic algorithm，BB-GA），運(yùn)用遺傳算法搜索給定調(diào)度解的總完工時間偏差最大的加工時間情景，再運(yùn)用分支定界方法從解空間中獲得min-max 準(zhǔn)則的魯棒調(diào)度解，如圖1所示。

圖1 BB-GA算法框架Fig.1 Framework of BB-GA

根據(jù)定理1，求解給定調(diào)度解的總完工時間最大偏差的加工時間向量，只需要搜索各加工時間區(qū)間的端點(diǎn)值即可。因此，遺傳算法可采用0-1編碼，染色體長度等于工件數(shù)量與機(jī)器臺數(shù)的乘積。采用這樣的方式解碼，染色體的各基因位依次對應(yīng)給定調(diào)度解的各加工時間，如果基因位是“0”，則相應(yīng)的工件加工時間取其區(qū)間下限，反之，基因位是“1”，則相應(yīng)的工件加工時間取其區(qū)間的上限，從而，染色體與加工時間向量一一對應(yīng)，實現(xiàn)了遺傳算法的編碼與解碼。

對于給定的調(diào)度解，遺傳算法的一條染色體對應(yīng)一種加工時間情景，那么，可以依據(jù)式求取該染色體對應(yīng)的總完工時間偏差，以此作為適應(yīng)度函數(shù)，進(jìn)行遺傳算法的種群選擇。從而，求取給定調(diào)度解的總完工時間最大偏差。

分支定界算法采用深度優(yōu)先策略，按照字典序依次搜索。對于搜索到的新的分支，如果部分序的下界小于已有的上界，或者不滿足定理2或定理3，則搜索下一個分支，否則，延長部分序的長度，計算其下界，并判斷對于定理2和定理3的滿足性。如果沿著一條路徑搜索到了最底層，也就是形成了完整的調(diào)度解，所有工件都已安排，驗證其總完工時間最大偏差是否小于已有的上界，如果小于已有的上界，則替代形成新的上界，并記錄該調(diào)度解，否則，按照深度優(yōu)先策略搜索下一路徑。依此，直至搜索完全部路徑。

用MD表示總完工時間最大偏差的最小值，σ表示字典序的當(dāng)前序列，σ′表示字典序的下一個序列，σl表示σ中l(wèi)個工件的部分序，σ(l)是σ中第l個工件，表示σl的總完工時間最大偏差下界，σR是所求解的魯棒調(diào)度。

算法步驟如下：

輸入：n個工件在兩臺機(jī)器上的加工時間區(qū)間。

輸出：總完工時間最大偏差最小值MD，及魯棒調(diào)度σR。

步驟1設(shè)定σ={1,2,…},n,l=1,MD為足夠大的初始值。

步驟2根據(jù)遺傳算法（GA）求解,如果≤MD，σl滿足定理2 和定理3，且l ＜n，則l=l+1，返回步驟2；否則，如果＞MD，或σl不滿足定理2或定理3，轉(zhuǎn)到步驟3。

步驟3如果l=n，轉(zhuǎn)到步驟4；否則，如果σ(l)＜n，則σ=σ′,返回步驟2，如果σ(l)=n,則σ=σ′,l=l-1,返回步驟2。

步驟4如果＜MD,則=MD,σR=σl；如果σ(1)=n,σ(n)=1,算法結(jié)束，輸出最大偏差的最小值MD和魯棒調(diào)度σR,否則，σ=σ′,返回步驟2。

在圖1中，算法的效果由運(yùn)用遺傳算法求解給定調(diào)度解的完工時間最大偏差，以及運(yùn)用分支定界求解完工時間最大偏差最小的調(diào)度解兩部分決定，由于分支定界算法是確定性算法，能夠得到最優(yōu)解，因此，算法效果主要取決于前者。

4 仿真實驗

4.1 實驗設(shè)計

仿真實驗硬件設(shè)備為配備Intel?CoreTMi9-11900K @3.5 GHz處理器的臺式計算機(jī)。

開展兩類實驗，一是針對給定調(diào)度方案，驗證遺傳算法求解其總完工時間最大偏差的優(yōu)越性；二是驗證求解的初始魯棒性調(diào)度方案的魯棒性。

4.2 總完工時間最大偏差的實驗分析

從每個問題中隨機(jī)產(chǎn)生10個實例，在每個實例中，對工件按照生成的先后次序進(jìn)行排序，以按照生成次序排序的調(diào)度方案作為給定調(diào)度方案。針對每個問題，對各實例分別運(yùn)用遺傳算法、模擬退火算法、禁忌搜索算法求解總完工時間最大偏差，以及隨機(jī)選取另外一個調(diào)度方案，求解其總完工時間偏差，然后求解10個實例總完工時間最大偏差的平均值。這幾類算法在智能優(yōu)化中具有典型性。結(jié)果如圖2所示。

圖2 總完工時間偏差最大值仿真結(jié)果Fig.2 Maximum deviation of total completion time

從圖2 可以看出，對于給定調(diào)度方案，遺傳算法求解的總完工時間偏差最大值大于其他各類算法，當(dāng)問題規(guī)模增大時，優(yōu)勢更為明顯。

4.3 初始調(diào)度方案魯棒性的實驗分析

（1）驗證指標(biāo)

從每個問題中隨機(jī)產(chǎn)生10 個實例，分別記錄和計算每個問題的10 個實例中最優(yōu)期望調(diào)度（以期望加工時間作為調(diào)度目標(biāo)求解的調(diào)度方案）σE的總完工時間最大偏差與魯棒調(diào)度σR的總完工時間最大偏差的最大比值MaxDev(E/R)、平均比值MeanDev(E/R)和最小比值MinDev(E/R)，魯棒調(diào)度σR的期望總完工時間與最優(yōu)期望調(diào)度σE的期望總完工時間的最大比值MaxTc(R/E)、平均比值MeanTc(R/E)和最小比值MinTc(R/E)。各指標(biāo)如表2所示。

（2）實驗結(jié)果

仿真實驗結(jié)果如表3所示。

在表3 中，第（1）列是問題編號，第（2）列是工件數(shù)目，第（3）和（4）列分別是α1和α2的均勻分布區(qū)間，第（5）到（10）列分別是表1給出的指標(biāo)。第（5）到第（10）列的各列中圓括弧標(biāo)出了各列的最小值，方括弧標(biāo)出了各列的最大值。

表1 實驗問題Table 1 Experimental questions

表2 計算實驗比較指標(biāo)Table 2 Indices of computational experiments

表3 計算實驗結(jié)果Table 3 Result of computational experiments

（3）實驗分析

從表3 可以看出，在各組問題中，最優(yōu)期望調(diào)度的總完工時間最大偏差都明顯大于魯棒調(diào)度，各組最大偏差比值的最大值高達(dá)2.458，最小值有1.484，各組平均偏差比值的最大值達(dá)到1.703，最小值為1.253，各組最小偏差比值的最大值有1.3，最小值也有1.042。從魯棒調(diào)度的期望調(diào)度目標(biāo)與期望調(diào)度的目標(biāo)比值來看，各組中最大比值的最大值只有1.114，平均比值的最大值僅有1.047，最小值為1.011，而各組最小比值的最大值僅為1.008，最小值則為1，也就是說二者有著相同的期望總完工時間。

圖3 展示了實驗結(jié)果，橫軸是問題，縱軸是比值，6條折線分別是表1 中的6 個指標(biāo)。圖2 中，對于8 個問題，指標(biāo)1、2和3明顯大于指標(biāo)4、5和6。而且，指標(biāo)4、5和6都接近于1。

圖3 實驗分析Fig.3 Experiment analysis

表3和圖3充分表明：

（1）魯棒調(diào)度能夠有效克服加工時間的不確定性的擾動，避免生成總完工時間偏差較大的調(diào)度方案；

（2）魯棒調(diào)度相比最優(yōu)期望調(diào)度的性能損失很小。

計算實驗驗證了本文的魯棒調(diào)度方法能夠生成總完工時間偏差較小，而性能損失較小的初始魯棒調(diào)度方案，能夠有效解決加工時間是區(qū)間數(shù)，以總完工時間為調(diào)度目標(biāo)的兩階段流水車間調(diào)度問題。

5 結(jié)語

本文研究了以總完工時間作為調(diào)度目標(biāo)，加工時間為區(qū)間數(shù)的兩階段流水車間魯棒調(diào)度問題，求解所有加工時間情景下，使得能夠獲得最優(yōu)調(diào)度目標(biāo)最大偏差最小的魯棒性初始調(diào)度方案，即Min-Max 準(zhǔn)則的魯棒調(diào)度。以總完工時間為調(diào)度目標(biāo)的調(diào)度問題作為研究對象，更符合實際生產(chǎn)需要。建立了該類魯棒調(diào)度問題的半無限規(guī)劃模型，證明了問題的一個簡化定理和兩個占優(yōu)定理，簡化定理將半無限規(guī)劃模型轉(zhuǎn)化為等價的有限約束的模型，占優(yōu)定理用以縮小解空間。建模與定理證明的理論價值顯著，對于類似問題的研究具有很好的借鑒意義。設(shè)計了求解的分支定界-遺傳算法，使用遺傳算法獲取給定調(diào)度解的完工時間最大偏差，分支定界算法搜索調(diào)度解，利用了遺傳算法的全局搜索性和分支定界的全局最優(yōu)性，混合算法效果良好。本文的研究對于生產(chǎn)以外的其他領(lǐng)域，還可以推廣應(yīng)用于供應(yīng)鏈、信息網(wǎng)絡(luò)等其他領(lǐng)域。