混合流水車間調度的自適應遺傳算法求解

軒轅佳慧

【摘 要】針對以最小化總流程時間為目標的混合流水車間調度問題，考慮到工業生產中并行機的異構或新舊程度等使得同一工序在不同工位的加工時間的不同，假設每個生產階段的并行機為不相關并行機，結合遺傳參數自適應動態調整機制，提出了一種自適應遺傳算法。基于不同規模問題的仿真實驗說明了所提出算法的有效性。

【關鍵詞】混合流水車間;不相關并行機;總流程時間;自適應遺傳算法

1.引言

混合流水車間調度問題（hybrid flow shop scheduling problem， HFSSP）在流程工業較為常見，如鋼鐵業、化工業等。按并行機的特點，可將HFSSP分為同構并行機、均勻并行機、不相關并行機調度問題[1]。由于兩階段HFSSP即使只有一個階段有多臺機器也是NP-hard的，因此求解HFSSP的方法多為近似算法。

在相同并行機環境下，關于HFSSP的近似算法多追求最小化最大完工時間，如韓忠華等[2]提出了改進帝國競爭算法;任彩樂等[3]設計了基于兩階段解碼方法的候鳥優化算法;吳秀麗和崔琪[4]考慮可再生能源提出集成低碳調度策略的快速非支配遺傳算法以同時最小化最大完工時間和碳排放量。

在不相關并行機環境下，吳楚格等[5]提出了解決并行機調度的基于信息熵的自適應分布估計算法，目標是最小化最大完工時間。針對HFSSP，為最小化最大完工時間，孟磊磊等[1]考慮了阻塞限制，提出了一種改進的回溯搜索算法;宋存利[6]提出了改進貪婪遺傳算法;王芳等[7]結合自適應調整模型設計了高效分布估算算法求解大規模調度問題;杜利珍等[8]提出了果蠅優化算法。

從上述研究現狀可發現，對于含不相關并行機的HFSSP的研究多為最大完工時間問題，缺乏對其它目標問題的探討。因此，為減少在制品庫存，本文以總流程時間為目標函數，設計結合遺傳參數自適應動態調整機制的遺傳算法，以有效求解該問題。

2.問題描述

本文所研究的混合流水車間調度問題可描述如下：J個工件經O道工序進行加工，每道工序i可由UPi臺不相關并行工位的任一個來完成，工件j在工序i中不同工位上的加工時間不同。

令bji、pji、fji分別表示工件j在工序i的開工時間、加工時間和完工時間;令Xjik為0-1變量，當工件j在工序i選擇工位k（k=1，2，...，UPi）加工時，其值為1，否則為0。則工件開工和完工時間之間有：fji=bji+∑kXjikpjik。為減少在制品庫存，所研究的HFSSP旨在追求總流程時間最小化，即確定工件在每道工序的工位分配以及同一工位上工件的加工序列以使所有工件的完工時間之和最小。因此，HFSSP的調度目標可表示為：

需滿足的約束條件有：

（1）所有工件在零時刻均可用于加工。

（2）工件j在工序i可選擇任一臺工位進行加工。選擇的工位不同，則它的加工時間也會不同。

（3）每個工位一次至多加工一個工件，而每個工件一次只能在一臺工位進行加工。

（4）同一時刻正在加工的工件數不能超過該工序的工位數。

（5）相鄰工位間的運輸時間忽略不計。

（6）相鄰工序間有無限緩沖區。

3.自適應遺傳算法設計

遺傳算法（genetic algorithm， GA）利用染色體進化實現種群的迭代，最終找到所求問題的近優解。為改進遺傳算法解，本文在執行GA的過程中設計了隨迭代進程而變化的計遺傳參數算公式，具體求解步驟如下：

（1）參數初始化。對種群規模、最大迭代數MG、當前迭代cg等進行初始化。

（2）初始種群生成。利用二維矩陣編碼機制隨機生成染色體矩陣，矩陣的每一行對應于一個工件在各工位的分配，即每個元素代表了對應工件在一道工序所分配的工位號，每一列則為各工件在同一工序的工位號。進而，計算每個個體的適應度值。

（3）選擇操作。應用輪盤賭規則從當前種群篩選出進入交叉和變異的染色體。適應度值越大的染色體被選中的概率越大。

（4）自適應遺傳參數設計。當個體適應度值Fz超過平均適應度值Favg時，計算當前最大適應度值Fmax與Favg的差值△F，交叉概率PC通過PC=PCmax-（PCmax-PCmin）/（cg/MG+Fz/△F）來獲取，變異概率PM通過PM= PMmin-（PMmax-PMmin）/（cg/MG+Fz/△F）計算得到。否則，令PC=PCmax，PM= PMmin。

（5）交叉操作。設計基于工件和基于工位的兩種單點倒置交叉方式。前者操作中，隨機選擇兩個父代染色體A和B，將A（B）的前a行和B（A）的后J-a行基因進行交叉組合生成子代染色體。后者操作中，隨機選擇一個工位號c，將染色體A（B）的前c列基因與染色體B（A）的后O-c列基因組合，從而形成新的染色體。根據交叉概率選擇上述交叉方式，得到新染色體。

（6）變異操作。應用單點變異方式，隨機選擇一個基因，將其重新產生，從而產生新個體。

（7）終止條件檢驗。當算法達到最大迭代數或運行時間達到限制時，程序停止。

4.仿真實驗

為了驗證算法的有效性，對于不同規模的問題，利用自適應遺傳算法進行仿真實驗。所有實驗均在處理器為AMD A8-4500M，1.9GHz，內存為4.00G的計算機上運行。J、O、UPi分別取值為{30， 40， 60， 70}，{3， 4， 5}，{4， 5}，假設每個階段并行機數相同，J、O、UPi的不同取值共產生了4×3×2=24種組合。考慮到時間成本，將最大運行時間設置為1200s，最大迭代次數設置為100。通過不同的實驗測試，將交叉概率和變異概率分別取為0.6和0.3。

利用上述數據運行所提算法，得到實驗結果如表1所示。從表1可知，對于不同規模問題，自適應遺傳算法在平均923.734秒內得到的平均目標值為5172，即所設計算法可在合理的計算時間內得到滿意的近優解。隨著問題規模的增加，執行算法所需時間也會有所增長。圖1表示四種規模問題下（O=4，UPi=5）的目標值變化趨勢，由此可知隨著問題規模的增大，算法的收斂效果越好，優勢越明顯。

5.結論

本文研究了不相關并行機環境下的混合流水車間調度問題，以總流程時間為目標函數提出了自適應遺傳算法進行求解。通過對不同規模實例進行仿真實驗，結果說明了所提出的算法能夠在可接受的計算時間內得到滿意的近優解。進一步的研究可探索運輸問題與上述調度的協同問題。

【參考文獻】

[1]孟磊磊， 張超勇， 任彩樂， 李振國， 任亞平. 求解帶有阻塞限制的HFSP的MILP模型與改進回溯搜索算法[J]. 2018， 29（22）： 2647-2658.

[2]韓忠華，孫越，史海波，林碩. 改進帝國競爭算法求解柔性流水車間排產問題[J].控制工程，2017， 24（8）： 1649-1655.

[3]任彩樂， 張超勇， 孟磊磊， 余俊， 洪輝. 基于改進候鳥優化算法的混合流水車間調度問題[J]. 計算機集成制造系統， 2019， 25（3）： 643-653.

[4]吳秀麗， 崔琪. 考慮可再生能源的多目標柔性流水車間調度問題[J]. 計算機集成制造系統， 2018， 24（11）： 2792-2807.

[5]吳楚格， 王凌， 鄭曉龍. 求解不相關并行機調度的一種自適應分布估計算法[J]. 控制與決策， 2016， 31（12）： 2177-2182.

[6]宋存利. 求解混合流水車間調度的改進貪婪遺傳算法[J]. 系統工程與電子技術， 2019， 41（5）： 1079-1086.

[7]王芳， 唐秋華， 饒運清， 張超勇， 張利平. 求解柔性流水車間調度問題的高效分布估算算法[J]. 自動化學報， 2017， 43（2）： 280-293.

[8]杜利珍， 王震， 柯善富， 熊子雪， 李新宇. 混合流水車間調度問題的果蠅優化算法求解[J]. 中國機械工程， 2019， 30（12）： 1480-1485.