等待時間受限的HFSP及其拉格朗日松弛算法

丁小麗，朱 軍，劉 昶

DING Xiao-li1,2, ZHU Jun1, LIU Chang1

（1.中國科學院沈陽自動化研究所，沈陽 110016；2.中國科學院大學，北京 100049）

0 引言

混合流水車間調度問題（Hybrid Flow-shop Scheduling Problem, HFSP）是由Salvador于1973年首先提出來的。HFSP是一類復雜的組合優化問題，它是標準的flow-shop調度和并行機調度問題的綜合，相當普遍地存在于化工、鋼鐵、制藥等流程工業中[1]。

等待時間受限的混合流水車間調度問題廣泛存在于鋼鐵生產，玻璃加工和塑料等行業，它的形成是由于生產過程中的高溫連續性，要求工件在相鄰兩個階段之間保持一定的溫度，例如在鋼鐵生產過程中的煉鋼-連鑄-熱軋過程中，連鑄機對溫度有嚴格的要求，為避免溫度降低影響鋼水質量，不允許鋼水在工序間有過長的等待時間。因此，可將兩階段之間的溫度要求轉換為對等待時間的要求，從而形成了等待時間受限的混合流水車間調度問題。

目前，關于等待時間受限的HFS調度問題的研究較少。文獻[2]研究了具有零緩沖能力和有限等待時間的多處理器HFS問題，以總加權拖期最小為目標，基于離散時間和混合整數線性規劃提出了一種精確求解算法。文獻[3]研究了以最小化makspan為目標的等待時間受限的HFSP，提出了一種啟發式-禁忌算法來求解。文獻[4]針對考慮交貨期和等待時間受限的HFS調度問題，提出了一種結合回溯和鄰域搜索的混合算法來進行求解。文獻[5]研究了以最小化生產等待時間為目標的帶工件和工位等待時間的混合流水車間調度問題，提出運用差分進化算法來進行求解。文獻[6]研究了以最小化各工件的提前/拖期懲罰和為目標的帶交貨期和釋放期的等待時間受限的HFS調度問題，采用約束滿足優化算法和指派規則的混合算法來進行求解。

Gupta J N D[7]已經證明即使只有兩個階段且其中只有一個階段包含多臺并行機的HFSP是NP難問題，因此，本文要研究的更為復雜的HFSP也是典型的NP難問題。拉格朗日松弛算法[8,9]是解決生產調度問題的有效方法之一，可用于NP難問題的求解，它通過將復雜約束引入到目標函數，可將原問題分解為多個簡單的容易求解的子問題，大大降低了問題的求解難度，可以獲得問題的近優解。目前對于等待時間受限的混合流水車間調度問題的求解在算法方面集中于精確求解算法或者智能優化類的近似算法。因此本文創新性的將拉格朗日松弛算法用于等待時間受限的混合流水車間調度問題研究中，拓展了拉格朗日松弛算法的應用范圍和混合流水車間[10,11]調度理論。

本文針對等待時間受限的混合流水車間調度問題，首先建立了以最小化加權完成時間為目標的HFSP模型，然后在此基礎上設計相關的拉格朗日松弛算法來進行求解，最后通過實驗數據驗證算法的可行性和有效性。

1 HFSP問題描述及建模

所研究的等待時間受限的HFSP可描述如下： n個工件在流水線上經過相同的s個階段的加工，每個階段上有Mj臺同構并行機，每個工件可以在階段j的任意一臺機器上進行加工，已知工件i在階段j的加工時間為pij，同時工件i在相鄰階段j和j+1之間的等待時間不超過一定的時間上限aj。其中，每臺機器一次最多加工一個工件，每一個工件在任意時刻最多只能在一臺機器上進行加工，且加工過程是連續的，不允許發生中斷。調度問題就是確定各個工件在各階段的加工完成時間Cij，從而使得總加權完成時間達到最小。

上述模型中目標函數(1)為所有工件的總加權完成時間。約束(2)表示機器容量約束，即同一時刻在同一階段進行加工的工件數不超過該階段的機器數；約束(3)表示同一工件在同一時刻最多只能在加工過程中的一個階段進行加工；約束(4)為工件的時間優先級約束，表示工件只有在完成上一階段的加工之后才能進入下一階段的加工；約束(5)表示工件在相鄰階段之間的等待時間不超過一定的上限；約束(6)～(8)表示機器占用約束；約束(9)和約束(10)為相關變量的取值范圍定義。

等待時間受限的HFSP調度問題模型就是在滿足約束(2)～(10)的條件下將工件安排到各階段的機器上進行加工，使得所有工件的總加權完成時間達到最小。

2 算法設計

拉格朗日松弛（LR）算法是解決生產調度問題的有效方法之一，可用于NP難問題的求解，它通過將復雜約束引入到目標函數，可將原問題分解為多個簡單的容易求解的子問題，大大降低了問題的求解難度，可以獲得問題的近優解。整個求解過程如下：首先通過引入一組拉格朗日乘子將復雜約束松弛到目標函數中，形成拉格朗日松弛問題；然后將得到的LR問題分解為一系列簡單的子問題進行求解，最后對于松弛問題的解一般需要通過可行化來構造原問題的可行解；重復上述過程直至達到停止準則。可行解的目標函數值提供了一個最優解的上界，而對偶目標函數值為最優解的一個下界，這樣拉格朗日松弛算法同時也為衡量解的質量提供了一個標準，解的質量可以通過兩者之間的對偶間隙來進行衡量（對偶間隙=[可行解的目標值-對偶目標值]/對偶目標值）。

從上節所建立的模型中可以看出，約束(3)～(5)都耦合了不同的階段，如果要基于階段進行分解需要將這三個約束都進行松弛，松弛的約束越多，所得到的對偶目標值就越松，而只有約束(2)耦合了不同的工件，因此，本文所設計的拉格朗日松弛算法采用基于工件進行分解的策略，下面將詳細的介紹拉格朗日松弛過程、子問題的求解、乘子的更新以及可行解的構造過程。

2.1 拉格朗日松弛

引入拉格朗日乘子向量 將約束(2)松弛到目標函數(1)中，形成下面的拉格朗日松弛問題：

滿足約束(3)～(10)和：

通過不斷的逼近對偶問題的上界得到拉格朗日對偶問題：

滿足約束(3)～(10)和(12)。

當乘子給定時，式(11)中的前半部分是一個常數，將后半部分基于工件進行分解，得到多個工件級子問題，工件i 的工件級子問題可表示為：

滿足約束(3)～(10)和(12)。整理后得到：

因此， ( )LR λ 可歸結為：

滿足式(3)～(10)和(12)。

2.2 子問題的求解

利用反向動態規劃來求解工件級子問題。當給定工件i和一組乘子時，利用以下遞推公式來計算出工件i在各個階段的累積函數值：

2.3 構造可行解

由于松弛了機器容量約束(2)，得到的松弛問題的解往往是不可行的，需要進行可行化，構造可行解的過程如下：首先根據得到的工件的完成時間計算出工件在各個階段的開始加工時間表。在每個加工階段，按照工件在該階段的開始加工時間的增序進行排列，依次將工件安排在可利用的機器上；然后檢查各個工件相鄰階段之間的等待時間是否滿足要求，如果某工件在相鄰兩階段之間的等待時間超過了給定的時間上限，則將該工件在前一階段的開始加工時間后移，與后一個工件進行兩兩交換，直到前后兩個階段之間的等待時間滿足要求為止。

2.4 更新拉格朗日乘子

采用次梯度算法來對拉格朗日乘子進行更新。主要步驟如下：

STEP1：迭代次數 1n= 時，初始化拉格朗日乘子及相關參數。

STEP3：更新乘子。根據下列式子更新拉格朗日乘子：

其中nπ 是n次迭代步長，nπ 通過下式計算得到：

上式中GU是當前得到的最優的可行目標值的上界；Gn是n次迭代的 ( )LR λ 值；ε初始值設為1，Gn上升時保持不變，當Gn在若干次迭代中未發生變化時則取其一半。

STEP4：判斷是否滿足停止條件。若對偶間隙小于一個很小的數或達到了最大迭代次數，程序停止；否則返回STEP2進行下一次迭代。

圖1為拉格朗日松弛算法流程圖。

圖1 拉格朗日松弛算法流程圖

3 仿真結果及分析

為了對所提出的拉格朗日松弛算法進行可行性和有效性的驗證，采用MATLAB對上述拉格朗日松弛算法進行編程，并在Intel(R) Core(TM) CPU 3.2GHz的計算機上運行。

分析表1～表3中的數據可以看出：

1）對于同一問題規模（當工件數和階段數一定時），隨著并行機器數的增加，可利用的機器資源增加，運行時間有所減少，對偶間隙也得到了改善；

2）對于同一規模問題，隨著相鄰階段之間的等待時間的增大，算法的運行時間相應加長，得到的解質量略有下降（對偶間隙略有增加）。即和對解的質量（對偶間隙）的影響很小，由此說明所設計的拉格朗日松弛算法對于不同的等待時間均能得到較好的近優解。

3）對于不同規模問題而言，時算法的運行時間隨之增加。且當由5增加到10時，運行時間有較大幅度的增加。

圖2為不同工件數在加工階段數為5，各個階段的機器數為4，等待時間為10的情況下對偶間隙隨迭代次數變化趨勢圖，三條曲線分別反應了工件數為10，20和40時的對偶間隙變化，從圖中可以看出：

1）所設計的拉格朗日松弛算法在迭代前期有較好的收斂速度，隨著迭代次數的增加，收斂速度逐漸減緩并最終趨向于收斂。

2）在加工階段和機器數量相同時，在同一迭代次數下，規模較大的問題的對偶間隙比規模較小的問題的對偶間隙要相對大一些，即規模較小的問題所得到的解的質量相對好一些。

表1 n=10的仿真結果

表2 n=20的仿真結果

表3 n=40的仿真結果

圖2 不同工件數時對偶間隙隨迭代次數變化趨勢

綜合上述分析可以看出，本文所設計的拉格朗日松弛算法能夠在較短的時間內產生較好的近優解，可以用于等待時間受限的混合流水車間調度問題中。

4 結束語

本文針對由于生產過程中的高溫連續性等要求而產生的等待時間受限的混合流水車間問題進行問題建模和算法的研究。首先建立了等待時間受限的混合流水車間調度問題模型，然后在此基礎上設計相應的拉格朗日松弛算法來進行求解。該算法通過將機器容量約束松弛到目標函數中，進而將得到的松弛問題分解為一系列易于求解的工件級子問題來進行求解，并利用動態規劃算法來求解子問題，然后對得到的松弛問題的解利用一種啟發式算法來進行可行化，并通過次梯度算法來不斷更新乘子。最后對設計的算法進行仿真驗證，測試結果表明所設計的拉格朗日松弛算法能夠在較短的時間內產生較好的近優解。

[1] 王凌,周剛,許燁,等.混合流水線調度研究進展[J].化工自動化及儀表,2011,38(1):1-8.

[2] Gicquel C,Hege L,Minoux M, et al. A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints[J].Computers & Operations Research, 2012,39(3):629-636.

[3] Liu S Y, Cui J S, Li Y. Heuristic-Tabu algorithm for hybrid flowshop scheduling with limited waiting time[A].Wuhan:Proceeding of the International Symposium on Computational Intelligence and Design[C].2008:233-237.

[4] 尹兆濤,李鐵克.考慮交貨期和等待時間受限的HFS調度問題的混合算法[J].工業工程,2009,12(1):79-83.

[5] 王長濤,劉春光,胡平東,等.混合流水車間等待時間優化研究[J]. 沈陽建筑大學學報(自然科學版),2012,28(2):368-374.

[6] 肖擁軍,李鐵克,尹兆濤.考慮特殊時間約束的混合流水車間調度[J].計算機工程與應用,2010,46(8):205-207,231.

[7] Gupta J N D. Two stage,hybrid flow-shop scheduling problem[J]. Journal of Operational Research Society,1988,39(1):359-364.

[8] 軒華,唐立新.實時無等待HFS調度的一種拉格朗日松弛算法[J]. 控制與決策,2006,21(4):376-380.

[9] 杜書魁.需準備時間的FFS調度的一種拉格朗日松弛算法[J].科學技術與工程,2012,12(6):1272-1277.

[10] 張其亮,陳永生.帶有阻塞限制的混合流水車間調度問題的混合粒子群求解算法[J].信息與控制,2013,42(2):252-257.

[11] 屈國強.瓶頸指向的啟發式算法求解混合流水車間調度問題[J]. 信息與控制,2012,41(4):514-521,528.