混合流水車間調(diào)度的自適應(yīng)遺傳算法求解

軒轅佳慧

【摘 要】針對(duì)以最小化總流程時(shí)間為目標(biāo)的混合流水車間調(diào)度問(wèn)題，考慮到工業(yè)生產(chǎn)中并行機(jī)的異構(gòu)或新舊程度等使得同一工序在不同工位的加工時(shí)間的不同，假設(shè)每個(gè)生產(chǎn)階段的并行機(jī)為不相關(guān)并行機(jī)，結(jié)合遺傳參數(shù)自適應(yīng)動(dòng)態(tài)調(diào)整機(jī)制，提出了一種自適應(yīng)遺傳算法?；诓煌?guī)模問(wèn)題的仿真實(shí)驗(yàn)說(shuō)明了所提出算法的有效性。

【關(guān)鍵詞】混合流水車間;不相關(guān)并行機(jī);總流程時(shí)間;自適應(yīng)遺傳算法

1.引言

混合流水車間調(diào)度問(wèn)題（hybrid flow shop scheduling problem， HFSSP）在流程工業(yè)較為常見(jiàn)，如鋼鐵業(yè)、化工業(yè)等。按并行機(jī)的特點(diǎn)，可將HFSSP分為同構(gòu)并行機(jī)、均勻并行機(jī)、不相關(guān)并行機(jī)調(diào)度問(wèn)題[1]。由于兩階段HFSSP即使只有一個(gè)階段有多臺(tái)機(jī)器也是NP-hard的，因此求解HFSSP的方法多為近似算法。

在相同并行機(jī)環(huán)境下，關(guān)于HFSSP的近似算法多追求最小化最大完工時(shí)間，如韓忠華等[2]提出了改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法;任彩樂(lè)等[3]設(shè)計(jì)了基于兩階段解碼方法的候鳥(niǎo)優(yōu)化算法;吳秀麗和崔琪[4]考慮可再生能源提出集成低碳調(diào)度策略的快速非支配遺傳算法以同時(shí)最小化最大完工時(shí)間和碳排放量。

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

從上述研究現(xiàn)狀可發(fā)現(xiàn)，對(duì)于含不相關(guān)并行機(jī)的HFSSP的研究多為最大完工時(shí)間問(wèn)題，缺乏對(duì)其它目標(biāo)問(wèn)題的探討。因此，為減少在制品庫(kù)存，本文以總流程時(shí)間為目標(biāo)函數(shù)，設(shè)計(jì)結(jié)合遺傳參數(shù)自適應(yīng)動(dòng)態(tài)調(diào)整機(jī)制的遺傳算法，以有效求解該問(wèn)題。

2.問(wèn)題描述

本文所研究的混合流水車間調(diào)度問(wèn)題可描述如下：J個(gè)工件經(jīng)O道工序進(jìn)行加工，每道工序i可由UPi臺(tái)不相關(guān)并行工位的任一個(gè)來(lái)完成，工件j在工序i中不同工位上的加工時(shí)間不同。

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

需滿足的約束條件有：

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

（2）工件j在工序i可選擇任一臺(tái)工位進(jìn)行加工。選擇的工位不同，則它的加工時(shí)間也會(huì)不同。

（3）每個(gè)工位一次至多加工一個(gè)工件，而每個(gè)工件一次只能在一臺(tái)工位進(jìn)行加工。

（4）同一時(shí)刻正在加工的工件數(shù)不能超過(guò)該工序的工位數(shù)。

（5）相鄰工位間的運(yùn)輸時(shí)間忽略不計(jì)。

（6）相鄰工序間有無(wú)限緩沖區(qū)。

3.自適應(yīng)遺傳算法設(shè)計(jì)

遺傳算法（genetic algorithm， GA）利用染色體進(jìn)化實(shí)現(xiàn)種群的迭代，最終找到所求問(wèn)題的近優(yōu)解。為改進(jìn)遺傳算法解，本文在執(zhí)行GA的過(guò)程中設(shè)計(jì)了隨迭代進(jìn)程而變化的計(jì)遺傳參數(shù)算公式，具體求解步驟如下：

（1）參數(shù)初始化。對(duì)種群規(guī)模、最大迭代數(shù)MG、當(dāng)前迭代cg等進(jìn)行初始化。

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

（3）選擇操作。應(yīng)用輪盤賭規(guī)則從當(dāng)前種群篩選出進(jìn)入交叉和變異的染色體。適應(yīng)度值越大的染色體被選中的概率越大。

（4）自適應(yīng)遺傳參數(shù)設(shè)計(jì)。當(dāng)個(gè)體適應(yīng)度值Fz超過(guò)平均適應(yīng)度值Favg時(shí)，計(jì)算當(dāng)前最大適應(yīng)度值Fmax與Favg的差值△F，交叉概率PC通過(guò)PC=PCmax-（PCmax-PCmin）/（cg/MG+Fz/△F）來(lái)獲取，變異概率PM通過(guò)PM= PMmin-（PMmax-PMmin）/（cg/MG+Fz/△F）計(jì)算得到。否則，令PC=PCmax，PM= PMmin。

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

（6）變異操作。應(yīng)用單點(diǎn)變異方式，隨機(jī)選擇一個(gè)基因，將其重新產(chǎn)生，從而產(chǎn)生新個(gè)體。

（7）終止條件檢驗(yàn)。當(dāng)算法達(dá)到最大迭代數(shù)或運(yùn)行時(shí)間達(dá)到限制時(shí)，程序停止。

4.仿真實(shí)驗(yàn)

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

利用上述數(shù)據(jù)運(yùn)行所提算法，得到實(shí)驗(yàn)結(jié)果如表1所示。從表1可知，對(duì)于不同規(guī)模問(wèn)題，自適應(yīng)遺傳算法在平均923.734秒內(nèi)得到的平均目標(biāo)值為5172，即所設(shè)計(jì)算法可在合理的計(jì)算時(shí)間內(nèi)得到滿意的近優(yōu)解。隨著問(wèn)題規(guī)模的增加，執(zhí)行算法所需時(shí)間也會(huì)有所增長(zhǎng)。圖1表示四種規(guī)模問(wèn)題下（O=4，UPi=5）的目標(biāo)值變化趨勢(shì)，由此可知隨著問(wèn)題規(guī)模的增大，算法的收斂效果越好，優(yōu)勢(shì)越明顯。

5.結(jié)論

本文研究了不相關(guān)并行機(jī)環(huán)境下的混合流水車間調(diào)度問(wèn)題，以總流程時(shí)間為目標(biāo)函數(shù)提出了自適應(yīng)遺傳算法進(jìn)行求解。通過(guò)對(duì)不同規(guī)模實(shí)例進(jìn)行仿真實(shí)驗(yàn)，結(jié)果說(shuō)明了所提出的算法能夠在可接受的計(jì)算時(shí)間內(nèi)得到滿意的近優(yōu)解。進(jìn)一步的研究可探索運(yùn)輸問(wèn)題與上述調(diào)度的協(xié)同問(wèn)題。

【參考文獻(xiàn)】

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

[2]韓忠華，孫越，史海波，林碩. 改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法求解柔性流水車間排產(chǎn)問(wèn)題[J].控制工程，2017， 24（8）： 1649-1655.

[3]任彩樂(lè)， 張超勇， 孟磊磊， 余俊， 洪輝. 基于改進(jìn)候鳥(niǎo)優(yōu)化算法的混合流水車間調(diào)度問(wèn)題[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2019， 25（3）： 643-653.

[4]吳秀麗， 崔琪. 考慮可再生能源的多目標(biāo)柔性流水車間調(diào)度問(wèn)題[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2018， 24（11）： 2792-2807.

[5]吳楚格， 王凌， 鄭曉龍. 求解不相關(guān)并行機(jī)調(diào)度的一種自適應(yīng)分布估計(jì)算法[J]. 控制與決策， 2016， 31（12）： 2177-2182.

[6]宋存利. 求解混合流水車間調(diào)度的改進(jìn)貪婪遺傳算法[J]. 系統(tǒng)工程與電子技術(shù)， 2019， 41（5）： 1079-1086.

[7]王芳， 唐秋華， 饒運(yùn)清， 張超勇， 張利平. 求解柔性流水車間調(diào)度問(wèn)題的高效分布估算算法[J]. 自動(dòng)化學(xué)報(bào)， 2017， 43（2）： 280-293.

[8]杜利珍， 王震， 柯善富， 熊子雪， 李新宇. 混合流水車間調(diào)度問(wèn)題的果蠅優(yōu)化算法求解[J]. 中國(guó)機(jī)械工程， 2019， 30（12）： 1480-1485.