基于異步次梯度法的LR算法及其在多階段HFSP的應用

軒 華， 李 冰

(鄭州大學 管理工程學院，河南 鄭州 450001)

?

基于異步次梯度法的LR算法及其在多階段HFSP的應用

軒 華， 李 冰

(鄭州大學 管理工程學院，河南 鄭州 450001)

為降低求解復雜度和縮短計算時間，針對多階段混合流水車間總加權完成時間問題，提出了一種結合異步次梯度法的改進拉格朗日松弛算法。建立綜合考慮有限等待時間和工件釋放時間的整數規劃數學模型，將異步次梯度法嵌入到拉格朗日松弛算法中，從而通過近似求解拉格朗日松弛問題得到一個合理的異步次梯度方向，沿此方向進行搜索，逐漸降低到最優點的距離。通過仿真實驗，驗證了所提算法的有效性。對比所提算法與傳統的基于次梯度法的拉格朗日松弛算法，結果表明，就綜合解的質量和計算效率而言，所提算法能在較短的計算時間內獲得更好的近優解，尤其是對大規模問題。

系統工程；異步次梯度法；拉格朗日松弛算法；多階段混合流水車間問題；總加權完成時間

0 引言

混合流水車間問題(HFSP)所處的制造環境一般可描述為：一組工件L={1, 2, …,M}按照相同的加工順序依次經過G個加工階段進行加工，每個階段g由mg臺同構并行機組成，且至少有一個加工階段的mg> 1；每個工件在每個階段至多在一臺同構機上加工；每臺機器任何時間至多只能加工一個工件而每個工件在任何時間也只能在一臺機器上加工。因此，HFSP要解決的問題是：將工件分配到機器上且確定在每個加工階段的機器上工件的調度，同時還要最優化某個給定的目標函數[1，2]。

本文研究了一類較為復雜的HFSP，該問題區別于一般的HFSP：

·工件b在相鄰兩個加工階段之間有等待時間限制；

·每個工件在時刻Fb(Fb≥1)才能用于加工；

·相鄰加工階段間的運輸時間不可忽略。

Gupta證明了兩階段HFSP是NP-hard，即使一個加工階段只有一臺機器。因此，本文所研究的更復雜的HFSP也是NP-hard[3]，這使得探討求解這類問題的近似算法顯得尤為重要。

拉格朗日松弛(LR)算法作為一種基于最優化的近似算法，其基本思想是分解和協調，對于實際調度問題通過合理的設計該算法可在合理的計算時間內獲得具有可量化質量的近優解[4]。傳統的LR算法通過引入拉格朗日乘子向量松弛機器能力約束，進而將形成的松弛問題分解為多個工件級子問題，利用動態規劃最優求解這些子問題，然后利用次梯度法更新乘子，利用啟發式將子問題的解轉換為原問題的可行解。重復上述過程直到滿足一定的停止條件。

然而，當實際問題規模較大時，利用動態規劃最優求解拉格朗日子問題的計算復雜度也隨之增大，這使得求解相當耗時。因此，本文在LR算法中引入了異步次梯度法，該方法是代理次梯度法的一種特殊情況[5]，它要求每次迭代最優求解一個拉格朗日子問題從而節約了計算時間，目的在于在較短的計算時間內得到大規模問題的較好解。

基于代理次梯度法的LR已被用于求解不同的生產調度問題。文獻[4,6,7]利用結合代理次梯度法的LR算法求解了單件車間調度，以提高準時傳送和降低在制品庫存。就總加權完成時間問題，文獻[8]研究了帶有限中間存儲的實時HFSP；文獻[9]則考慮了可重入HFSP。文獻[10]求解了帶順序相關調整影響(時間和費用)的HFSP，目標是降低在制品庫存和調整費用。文獻[11]求解了煉鋼-連鑄生產調度問題，該過程可視為HFS結構，目標是減少斷澆、降低爐次在加工階段間的等待時間和滿足準時傳送要求。

就目前所查閱的資料來看，近年來基于代理次梯度法的LR在HFSP的優化研究較少，且既有研究缺乏對有限等待等實際生產特征的探討。而對于不同的生產調度問題有必要研究算法的具體實現方式以得到滿意解。因此，以總加權完成時間為目標，本文研究了求解帶等待考慮的HFSP的嵌入異步次梯度法的LR的有效性，擴展了LR算法理論及其應用。

1 多階段HFSP描述

本文所研究的HFSP是在G個階段的同構并行機上按照相同的加工順序調度M個工件，目標是最小化總加權完成時間以降低在制品庫存。工件在相鄰加工階段間的等待時間不允許超過等待上限。假定每個操作不允許中斷，每個工件在時刻Fb才能開始加工，運輸時間不可忽略。

1.1 符號說明

已知參數：M為總工件數；G為總階段數；mg為階段g可利用的機器數；Obg為工件b(b=1,2,…,M)在階段g(g=1,2,…,G)的加工時間;Fb為工件b的釋放時間;Gg,g+1為階段g和g+1的運輸時間;Ubg工件b在相鄰階段g和g+1間的等待上限;K為總計劃時間水平。

決策變量：Cbg為工件b在階段g的完工時間;Xbgt為0-1變量，若工件b在時刻t正在階段g上加工，則其值為1，否則為0.g=1,2,…,G;b=1,2,…,M;t=1,2,…,K。

1.2 整數規劃模型

(1)

滿足

Cbg≤Cb,g+1-Obg-Dg,g+1,b=1,…,M;g=1,…,G-1

(2)

(3)

Cbg-Obg+1≤t+K(1-Xbgt),b=1,…,M;g=1,…,G;t=1,…,K

(4)

tXbgt≤Cbg,b=1,…,M;g=1,…,G;t=1,…,K

(5)

Cb,g+1-Ob,g+1-Dg,g+1-Cbg≤Ubg,b=1,…,M;g=1,…,G-1

(6)

(7)

Cb1-Ob1+1≥Fb,b=1,…,M

(8)

Xgbt∈{0, 1},b=1,…,M;g=1,…,G;t=1,…,K

(9)

Cbg∈{1,2, …,K},b=1,…,M;g=1,…,G

(10)

文獻[12]也建立了帶有限等待HFSP的數學模型，但是本文的目標是滿足上述所有約束的條件下最小化總加權完成時間，而[12]則還考慮了等待懲罰。

約束(2)表示了一個工件在加工階段間的操作優先級；約束(3)～(5)定義了每個工件在加工階段上占用機器的時間間隔；約束(6)表示了工件在階段g完成加工且送達階段g+1之后的等待時間不能超過等待上限；約束(7)說明了所有機器需求都要滿足當時可利用的機器數；約束(8)說明了每個工件只有在其到達生產系統始端才能開始加工；約束(9)～(10)定義了變量的取值范圍。

2 求解框架

基于工件分解策略，將機器能力約束通過引入拉格朗日乘子松弛到目標函數中，松弛能力約束的目的在于使得松弛后的問題可分解為多個相對容易求解的工件級子問題。

2.1 松弛和分解

引入拉格朗日乘子向量ψ(其分量為{ψgt})，將約束(7)松弛到目標函數中，形成拉格朗日松弛問題：

滿足約束(2)～(6),(8)～(10)和

ψgt≥0,g=1,2,…,G;t=1,2,…,K

(11)

則拉格朗日對偶問題是

(12)

滿足約束(2)～(6),(8)～(11)。

給定{ψgt}，工件b的工件級子問題Hb(ψ)為：

(13)

滿足約束(2) ～(6), (8)～(11)。

圖1 兩級分解-協調結構

2.2 分解和協調

圖1顯示了LR算法的兩級分解-協調結構。在“低級”，已知乘子{ψgt}的條件下求解M個工件級子問題；在“高級”，基于約束違反的程度更新乘子{ψgt}，然后根據子問題的解設計啟發式將其轉換成可行解，直到迭代過程結束[4]。

所設計的LR算法與傳統LR算法不同之處在于所設計的算法在每次迭代近似求解子問題以及利用了異步次梯度法[5]在“高級”更新乘子。

3 子問題的近似求解和可行解的構造

3.1 子問題

給定某工件B和乘子{ψgt}，后向動態規劃最優求解的遞歸關系式為：

(14)

(15)

3.2 可行解的構造

基于上述得到的松弛問題的解，對每個階段g，按照工件在該階段的開始時間的增序排列，然后依次將其分配到可利用的機器上，若相鄰加工階段間的等待時間超過Ubg，則延遲該工件在階段g-1的開始時間直到滿足等待時間約束。

4 對偶問題

傳統的次梯度法要求每次迭代最優求解所有拉格朗日子問題以得到次梯度方向，因此當問題規模較大時，松弛問題的求解較為復雜且費時。為此，設計了異步次梯度法[5]以減少每次迭代所耗費的求解時間，它在每個子問題求解后即可更新乘子。

代理對偶函數定義為：

(16)

則代理次梯度定義為:

(17)

異步次梯度法的執行過程如下：

步驟0 初始化ψ0，最小化所有子問題得到X0，即

計算對偶費用和次梯度，沿次梯度方向更新乘子。令子問題標號p= 1。

步驟1 已知第s次迭代的ψs，最優求解第p個子問題，同時保持其它子問題的解不變，根據式(16)和(17)分別計算代理對偶費用和代理次梯度。

步驟2 由上步得到的ψs和Xs，更新拉格朗日乘子：

(18)

其中步長α定義為：

(19)

步驟3 令p=p+1，如果p>M，則重設p=1。

步驟4 如果CPU時間達到某個限定值或代理對偶間隙小于很小的數，程序停止，否則返回步驟1。

5 仿真實驗

利用C語言在PC(2.10GHz CPU)執行所設計的算法，仿真實驗將該算法與傳統的基于次梯度法的LR進行了比較。首先，對中小規模問題進行測試說明兩種算法的有效性；然后比較實際大規模問題的運行結果以估計實際規模問題的性能。

所測試問題的最大規模是200個工件，4個階段，5臺并行機。對于每組{M,G,mg}隨機產生10個實例；在每個實例中，每個工件的數據隨機產生如下：權重和加工時間滿足均勻分布U[1,10]，釋放時間滿足均勻分布U[1,5]。相鄰加工階段間的運輸時間滿足均勻分布U[1,3]。等待時間取為5, 15。總時間水平設為所有加工時間之和。算法在90秒后終止。

用LR-ISG表示基于異步次梯度法的LR，用LR-SG表示傳統的基于次梯度法的LR。以對偶間隙和迭代數來衡量兩種算法的性能指標。SDG定義為代理對偶間隙(%)，其值等于(UB-SLB)/SLB×100%，DG為真正對偶間隙，由(UB-LB)/LB×100%計算得到，IN表示迭代數，這里，UB表示可行費用，即原問題的上界；LB表示對偶費用，即下界；SLB為代理對偶費用。

5.1 實例1

本節測試了40和80個工件的情況，計算結果顯示在表1～2中，表中的結果(除最后一行外)為同一規模的10組實例的平均值。從表中可得知：

(1)對于40個工件的情況，當U=5和15時由LR-ISG得到的平均對偶間隙分別為2.64%和3.09%，LR-SG得到的分別為2.97%和3.26%，因此，所提算法比傳統LR得到的對偶間隙平均降低0.33%和0.17%。

(2)對于80個工件的情況，當U=5和15時由LR-ISG得到的平均對偶間隙分別為5.22%和6.04%，LR-SG得到的分別為5.46%和7.99%，因此，所提算法比傳統LR得到的對偶間隙平均降低0.24%和1.95%。

(3)在相同的計算時間內，LR-ISG執行的迭代數是LR-SG的幾十倍，這是由于LR-ISG每次迭代只最優求解一個子問題所耗費的計算時間比最優求解所有子問題要少得多。

(4)當U=5和15時，LR-ISG的代理對偶間隙與真正對偶間隙的偏差分別為0.04%和0.05%(對于40個工件)，0.38%和0.49%(對于80個工件)，即LR-ISG得到的代理對偶間隙和真正對偶間隙相差不大。

綜上可知，對中小規模問題，這兩種算法都能在較短的計算時間(90s)內得到很好的近優解，且所提出的LR算法表現略佳。

表1 M=40的測試結果

表2 M=80的測試結果

表3 M=120的測試結果

表4 M=150的測試結果

表5 M=200的測試結果

5.2 實例2

本節測試的工件數取自{120,150,200}，測試結果如表3～5所示，從表中結果可得到如下結論：

(1)當U=5時，對于120個工件，150個工件和200個工件的情況，LR-ISG分別在在5492次，3732次和1939次迭代得到的平均代理對偶間隙為5.44%，5.25%，5.34%；真正的對偶間隙分別為6.49%，6.70%，7.83%。由LR-SG分別在140次，90次和51次迭代得到的對偶間隙為8.20%，10.86%，18.79%。因此，LR-ISG的對偶間隙比LR-SG降低1.71%，4.16%，10.96%。

(2)當U=15時，對于120個工件，150個工件和200個工件的情況，LR-ISG分別在在4130次，2900次和1860次迭代得到的平均代理對偶間隙為6.94%，7.32%，8.63%；真正的對偶間隙分別為8.49%，9.60%，13.56%。由LR-SG分別在59次，36次和18次迭代得到的對偶間隙為16.54%，27.42%，51.97%。因此，LR-ISG的對偶間隙比LR-SG降低8.05%，17.82%，38.41%。

(3)當U=5和15時，LR-ISG的代理對偶間隙與真正對偶間隙的偏差分別為1.05%和1.55%(對于120個工件)，1.45%和2.28%(對于150個工件)，2.49%和4.93%(對于200個工件)，即隨著問題規模的增大，LR-ISG得到的代理對偶間隙和真正對偶間隙相差也越大。

綜上可知，LR-ISG對于大規模問題能在較短的計算時間(90s)內得到很好的近優解，在解的質量和計算效率方面，LR-ISG明顯優于LR-SG。

6 結束語

本文針對考慮等待的HFSP設計了嵌入異步次梯度法的改進LR算法，目標是最小化總加權完成時間。通過松弛問題的近似求解簡化每次迭代的計算復雜度和所需的計算時間，進而得到一個合理的異步次梯度方向以搜索更好的解。仿真實驗結果表明在求解小到大規模問題時所提出的算法能夠在較短的計算時間內獲得很好的近優解，尤其對于實際大規模問題，它的性能明顯優于傳統LR。進一步的工作可將該方法推廣到具有其它生產特征的復雜生產調度問題中。

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

[2] Niu Q, Zhou T, Fei M, Wang B. An efficient quantum immune algorithm to minimize mean flow time for hybrid flow shop problems[J]. Mathematics and Computers in Simulation, 2012, 84: 1-25.

[3] Gupta J N D. Two-stage hybrid flowhsop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39: 359-364.

[4] Chen H X, Luh P B. An alternative framework to Lagrangian relaxation approach for job shop scheduling[J]. European Journal of Operational Research, 2003, 149(3): 499-512.

[5] Zhao X, Luh P B, Wang J. Surrogate gradient algorithm for lagrangian relaxation[J]. Journal of Optimization Theory and Application, 1999, 100(3): 699-712.

[6] Sun T, Luh P B, Liu M. Lagrangian Relaxation for complex job shop scheduling[C]. Proceedings of the IEEE International Conference on Robotics and Automation, Orlando, Florida, May 15-19, 2006, 1432-1437.

[7] Wang J, Luh P B, Zhao X, Wang J. An optimization-based algorithm for job shop scheduling[J]. SADHANA(a Journal of Indian Academy of Sciences on Competitive Manufacturing Systems), 1997, 22: 241-256.

[8] Tang L, Xuan H. Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers[J]. Journal of the Operational Research Society, 2006, 57(3): 316-324.

[9] Jiang S, Tang L. Lagrangian Relaxation algorithms for re-entrant hybrid flowshop scheduling[C]. International Conference on Information Management, Innovation Management and Industrial Engineering, Taipei, December 19-21, 2008, 78- 81.

[10] Liu C Y, Chang SC. Scheduling flexible flow shops with sequence-dependent setup effects[J] IEEE Transactions on Robotics and Automation, 2000, 16(4): 408- 419.

[11] Sun L, Chai T, Luh P B. Scheduling of steel-making and continuous casting system using the surrogate subgradient algorithm for Lagrangian relaxation[C]. 6th annual IEEE Conference on Automation Science and Engineering, Toronto, Ontario, Canada, August 21-24, 2010, 885- 890.

[12] 軒華.帶有限等待的動態HFS調度的拉格朗日松弛算法[J].工業工程與管理,2013,18(3):24-29.

Lagrangian Relaxation Using Interleaved Subgradient Method and Its Application for Multi-stage HFSP

XUAN Hua, LI Bing

(SchoolofManagementEngineering,ZhengzhouUniversity,Zhengzhou450001,China)

In order to reduce solution complexity and computation time, an improved Lagrangian relaxation algorithm combined with an interleaved subgradient method is presented to solve total weighted completion time problem of multi-stage hybrid flowshop. An integer programming model is firstly formulated for HFSP considering finite waiting time and job release time. An interleaved subgradient method is then introduced into Lagrangian relaxation which requires approximately solving Lagrangian relaxation problem to obtain a reasonable interleaved subgradient direction. The distance to optimal solutions can be decreased step by step along this searching direction. Computation experiments demonstrate the effectiveness of the presented algorithm. Compared with regular Lagrangian relaxation based on subgradient optimization, the testing results show that the developed method can get better schedule results with less time in aspect of solution quality and computation efficiency, especially for large-sized problems.

systems engineering; interleaved subgradient method; Lagrangian relaxation; multi-stage hybrid flowshop problem; total weighted completion time

2014- 05- 12

國家自然科學基金資助項目(71001090,71001091);中國博士后科學基金資助項目(2013M531683,2014T70684);教育部人文社會科學研究青年基金項目(15YJC630148)；鄭州大學優秀青年教師發展基金項目(1421326092);河南省科技攻關計劃資助項目(142102310335,142102310313)

軒華(1979-)，女，河南睢縣人，教授，博士，研究方向：生產計劃與調度、物流優化與控制;李冰(1976-)，男，河南省開封市人，教授，博士，研究方向：物流管理等。

TB399

A

1007-3221(2015)06- 0121- 07

10.12005/orms.2015.0203