基于遺傳算法的FMS系統(tǒng)排產(chǎn)算法設(shè)計(jì)＊

段 昭 徐寧波 包壁禎 徐衛(wèi)剛 王 巍 羅 陽 劉曉宇

（①成都四威高科技產(chǎn)業(yè)園有限公司，四川 成都 610097；②四川大學(xué)機(jī)械工程學(xué)院，四川 成都 610065）

柔性制造系統(tǒng)（flexible manufacturing system，F(xiàn)MS）[1]是一種技術(shù)復(fù)雜、高度自動(dòng)化的系統(tǒng)，它依靠有限的共享資源來實(shí)現(xiàn)多樣化零部件的生產(chǎn)，具有提高設(shè)備利用率、增加系統(tǒng)靈活性以及降低生產(chǎn)成本等優(yōu)點(diǎn)。在柔性制造系統(tǒng)中，需要控制系統(tǒng)、數(shù)控設(shè)備和工件儲(chǔ)運(yùn)系統(tǒng)進(jìn)行有機(jī)結(jié)合，按照任務(wù)順序?qū)ぜM(jìn)行加工，其核心是作業(yè)車間調(diào)度管理。它是將車間的有限資源在一定時(shí)間內(nèi)分配給若干任務(wù)，以實(shí)現(xiàn)或優(yōu)化一個(gè)或多個(gè)目標(biāo)，將直接影響車間資源配置和生產(chǎn)效率。FMS系統(tǒng)作業(yè)車間調(diào)度問題，需要在多個(gè)目標(biāo)之間進(jìn)行比較，可能存在相互矛盾等問題，因此設(shè)計(jì)合理的排產(chǎn)算法對(duì)于柔性制造系統(tǒng)至關(guān)重要。特別是在混流加工場(chǎng)景中，一個(gè)柔性制造系統(tǒng)內(nèi)包含多種類型的加工設(shè)備。由于設(shè)備類型、刀具類型和加工工藝存在差異，同一種零件的同一道工序在不同類型設(shè)備上的加工時(shí)長(zhǎng)也存在差異。正是由于這種差異的存在，每個(gè)任務(wù)選擇在哪一臺(tái)機(jī)床上，按照何種順序進(jìn)行加工，將會(huì)直接影響整批加工任務(wù)的總體加工時(shí)間。因此，排產(chǎn)算法的選擇和設(shè)計(jì)對(duì)于混流加工場(chǎng)景中的作業(yè)車間調(diào)度具有非常重要的意義。

國(guó)內(nèi)外學(xué)者對(duì)FMS系統(tǒng)的排產(chǎn)算法設(shè)計(jì)展開了深入研究。針對(duì)柔性車間作業(yè)排產(chǎn)問題，Zuo X Q 等[2]采用多目標(biāo)變鄰域免疫算法對(duì)一組工作流模型的FJSSP 問 題 （ flexible job shop scheduling problem）進(jìn)行了建模及研究。Sun J H 等[3]提出一種混合多目標(biāo)進(jìn)化算法用來解決多目標(biāo)柔性加工車間的靈活作業(yè)調(diào)度問題，其優(yōu)化目標(biāo)為最小化制造時(shí)間、總工作量、關(guān)鍵機(jī)器的工作量以及對(duì)完工時(shí)間的提前與延后進(jìn)行獎(jiǎng)勵(lì)與懲罰，通過具有鄰域結(jié)構(gòu)的禁忌搜索來提高局部搜索能力，進(jìn)而指導(dǎo)算法向pareto最優(yōu)前沿進(jìn)行探索逼近。Caldeira R H等[4]提出一種改進(jìn)的 Jaya（multi-objective jaya algorithm，MOJAYA）算法，算法中加入一種有效的初始化機(jī)制和局部搜索技術(shù)，改進(jìn)的Jaya算法可以改善元啟發(fā)式算法在尋找最優(yōu)解時(shí)陷入局部最優(yōu)的問題。針對(duì)不確定環(huán)境中的柔性車間調(diào)度問題，Shen X N等[5]開發(fā)了一種改進(jìn)的基于分解的多目標(biāo)進(jìn)化算法，該算法采用一種利用全局信息的子問題更新方法，允許保留種群中參與的精英子代，采用子問題選擇和暫停策略將更多計(jì)算工作集中用于適應(yīng)程度更好的子問題上，并結(jié)合特定問題的遺傳算子對(duì)子代進(jìn)行變異，使子代向最優(yōu)解有更好的收斂性能。

上述文獻(xiàn)中的FMS系統(tǒng)作業(yè)車間調(diào)度問題，大多數(shù)工序是按照零件順序進(jìn)行排列的，排產(chǎn)情況不夠復(fù)雜。為了進(jìn)一步提高排產(chǎn)算法的性能，本研究針對(duì)FMS系統(tǒng)中的復(fù)雜作業(yè)車間調(diào)度問題，利用遺傳算法進(jìn)行排產(chǎn)算法設(shè)計(jì)，分別從超期作業(yè)數(shù)、總超期時(shí)間、機(jī)床綜合負(fù)載率、最大機(jī)床負(fù)載率及作業(yè)完工時(shí)間等5個(gè)方面對(duì)排產(chǎn)結(jié)果進(jìn)行了對(duì)比。通過調(diào)整遺傳算法的種群規(guī)模、迭代次數(shù)以及遺傳交叉概率，選擇更優(yōu)的排產(chǎn)方案。

1 問題描述

1.1 問題描述

FMS系統(tǒng)加工車間調(diào)度問題可以描述為：在機(jī)床集合M上安排作業(yè)集合Jop，作業(yè)集合J表示為：Jop={Jop0,Jop1, ···,Jopn}；作業(yè)Jopi包含ni個(gè)加工工序，i=1, ···,N；車間中有M臺(tái)生產(chǎn)設(shè)備可用，表示為{M1,M2, ···,Mn};工件的每一道工序可以在任意一臺(tái)滿足加工要求的加工設(shè)備上完成。在給定機(jī)床工作日歷以及作業(yè)工序、生產(chǎn)時(shí)間和交貨期的條件下，求解設(shè)備負(fù)載均衡且生產(chǎn)周期最短的最優(yōu)排產(chǎn)方案。

1.2 約束條件

（1）每個(gè)作業(yè)（工件）只需在生產(chǎn)線上安排一次加工，作業(yè)工序只需在一臺(tái)機(jī)床上加工一次，且作業(yè)工序不可中斷或暫停。

（2）作業(yè)的工序順序不隨排產(chǎn)的方案發(fā)生變化，但加工時(shí)間可能隨機(jī)床選擇變化。

（3）機(jī)床在同一時(shí)刻只能加工一個(gè)作業(yè)工序。

1.3 目標(biāo)函數(shù)及數(shù)學(xué)模型

其中：

其中：

F1：超期作業(yè)數(shù)。所有不能在交貨期中完成的作業(yè)數(shù)。作業(yè)完工時(shí)間Ci是指在工作日歷上其最后一道工序完成時(shí)刻，di為作業(yè)交貨期。

F2：總超期時(shí)間。生產(chǎn)線上所有超期零件實(shí)際超期時(shí)間。

F3：機(jī)床綜合負(fù)載率。機(jī)床負(fù)載率描述每臺(tái)設(shè)備的工作負(fù)荷，即每臺(tái)設(shè)備停機(jī)之前實(shí)際加工時(shí)間與總工作時(shí)間之比。機(jī)床綜合負(fù)載率是個(gè)機(jī)床負(fù)載率之和，描述了生產(chǎn)線上設(shè)備的工作負(fù)荷的總體情況。其中Bij（i= 0, 1, ···,n）為機(jī)床j上所有完工工序的加工時(shí)間，Tj為機(jī)床j的停機(jī)時(shí)間。

F4：最大機(jī)床負(fù)載率。描述生產(chǎn)線上瓶頸機(jī)床的最大負(fù)載率。

F5：作業(yè)完工時(shí)間。

2 算法設(shè)計(jì)

遺傳算法[6]是模擬自然界中遺傳機(jī)制和自然選擇過程而提出的，包括編碼、交叉、變異和選擇等操作步驟。本研究針對(duì)FMS系統(tǒng)生產(chǎn)調(diào)度問題的多約束、多維度求解的特異性，利用遺傳算法進(jìn)行排產(chǎn)方案設(shè)計(jì)與對(duì)比。

2.1 染色體對(duì)編碼

作業(yè)車間調(diào)度要解決兩個(gè)問題[7]：一是生產(chǎn)過程和生產(chǎn)設(shè)備的匹配問題；二是工序排序問題。在利用遺傳算法時(shí)，需要將這兩種信息納入到染色體的編碼中。根據(jù)生物染色體遺傳機(jī)制，在本研究中將帶有工件信息的染色體設(shè)計(jì)為兩條：其中一條染色體表示工件工序信息，稱為工序基因鏈；另一條染色體表示工件加工所在加工設(shè)備信息，稱為設(shè)備基因鏈。假設(shè)有3個(gè)需要加工的工件，其中工件1有3道工序，工件2和工件3有兩道工序，加工設(shè)備有4臺(tái)，一種可行的調(diào)度方案如圖1所示。

圖1 染色體編碼方式

圖1中第一行為工序基因鏈，工序基因鏈中數(shù)字1、2、3表示工件編號(hào)，工件編號(hào)數(shù)字出現(xiàn)的次數(shù)代表工件加工需要進(jìn)行的工序數(shù)量。即工件1有3道工序，工件2和工件3有2道工序。第二行為設(shè)備基因鏈，該基因鏈中數(shù)字與工序基因鏈中數(shù)字為一一對(duì)應(yīng)關(guān)系，其中的數(shù)字為加工設(shè)備編號(hào)，即工件1的第一道加工工序在編號(hào)為1的加工設(shè)備上進(jìn)行，工件2的第一道加工工序在編號(hào)為3的加工設(shè)備上進(jìn)行，工件2的第二道加工工序在編號(hào)為4的加工設(shè)備上進(jìn)行，依此類推。

2.2 交叉算子

根據(jù)本研究中的染色體編碼結(jié)構(gòu)，對(duì)染色體基因中的基因片段進(jìn)行交叉[8]。由程序產(chǎn)生隨機(jī)數(shù)確定交叉基因片段的起始點(diǎn)與終點(diǎn)，將兩組染色體的對(duì)應(yīng)片段進(jìn)行交叉操作，如圖2所示。

圖2 交叉操作示意圖

交叉操作后的染色體可能會(huì)導(dǎo)致加工工件的工序數(shù)量出現(xiàn)錯(cuò)誤。圖中將父代染色體第四位到第五位進(jìn)行交叉操作，得到的染色體中工序基因鏈中工件2有3道工序、工件3有1道工序，這與要求中工件2和工件3有兩道工序相矛盾，因此需要進(jìn)行校驗(yàn)，保證染色體中包含工件信息正確。為確保染色體的多樣性，保證染色體交換片段信息不變，對(duì)交換片段以外的染色體片段從左到右進(jìn)行校驗(yàn)。

2.3 變異算子

編譯操作與交叉操作相互配合完成進(jìn)化過程，增加染色體的多樣性。在變異操作中，通過隨機(jī)數(shù)確定染色體變異片段的起始點(diǎn)與終點(diǎn)。將選中的基因片段進(jìn)行前后顛倒，并對(duì)工件工序?qū)?yīng)的加工設(shè)備進(jìn)行變異，從而產(chǎn)生更多的排產(chǎn)方案[9]。這種方法可以有效平衡設(shè)備的工作負(fù)擔(dān)，有利于縮短完工時(shí)間。變異操作如圖3所示。

圖3 變異操作示意圖

2.4 選擇操作

選擇操作即遺傳操作后染色體的保留方法，本研究使用貪婪準(zhǔn)則[10]進(jìn)行選擇。將變異操作后的子代與父代染色體進(jìn)行混合，通過目標(biāo)函數(shù)計(jì)算不同染色體對(duì)排產(chǎn)問題的適應(yīng)操作。根據(jù)對(duì)目標(biāo)函數(shù)的適應(yīng)情況，將混合后的種群進(jìn)行評(píng)價(jià)并排序，選取適應(yīng)能力更強(qiáng)的前一半個(gè)體進(jìn)行保留，去除剩下適應(yīng)能力較弱的個(gè)體。通過選擇操作保證種群的穩(wěn)定性。

2.5 基于遺傳算法的調(diào)度流程

（1）根據(jù)加工任務(wù)需求，設(shè)定待加工工件數(shù)量、各工件的工序數(shù)量、滿足各工序生產(chǎn)要求的生產(chǎn)設(shè)備；確定遺傳算法參數(shù)，包括種群規(guī)模、交叉概率、變異概率和迭代次數(shù)。

（2）隨機(jī)生成初始種群，根據(jù)零件數(shù)量、工序以及滿足工序要求的加工設(shè)備，隨機(jī)生成工序基因鏈與設(shè)備基因鏈。

（3）按照參數(shù)設(shè)定多個(gè)交叉概率、變異概率執(zhí)行交叉編譯操作，完成染色體的進(jìn)化過程。

（4）將父代和子代進(jìn)行混合，使用貪婪準(zhǔn)則選擇保留的個(gè)體，進(jìn)行迭代。

（5）完成迭代操作，輸出適應(yīng)能力最強(qiáng)的染色體，算法結(jié)束。

3 實(shí)驗(yàn)及結(jié)果分析

在本研究中設(shè)置一個(gè)柔性加工車間調(diào)度任務(wù)，車間中放置8臺(tái)加工設(shè)備，待加工工件為8件，每個(gè)工件最多包含4道加工工序，假設(shè)該批次零件要求在16 h內(nèi)完成加工。每道工序在各個(gè)生產(chǎn)設(shè)備上的加工時(shí)間如表1所示。

表1 工序加工時(shí)間

3.1 實(shí)驗(yàn)結(jié)果

通過調(diào)整種群規(guī)模、交叉概率、變異概率和迭代次數(shù)這4項(xiàng)參數(shù)對(duì)比排產(chǎn)結(jié)果。

第1種方案：種群規(guī)模為50，交叉概率為0.8，變異概率為0.2，迭代次數(shù)為1 000次。由排產(chǎn)結(jié)果甘特圖（圖4）可知，在該組排產(chǎn)方案中，零件最短加工完成時(shí)間為 17 h，有3個(gè)零件未在規(guī)定時(shí)間內(nèi)完成加工，超出規(guī)定完成時(shí)間1 h，加工設(shè)備最大利用率為82%。在該組參數(shù)下，加工設(shè)備利用率較低，存在超期完成加工的現(xiàn)象，部分加工設(shè)備利用率較低，排產(chǎn)結(jié)果不太理想。

圖4 第 1 種參數(shù)方案的排產(chǎn)甘特圖

第2種方案：種群規(guī)模為100，交叉概率為0.8，變異概率為0.2，迭代次數(shù)為2 000次。由排產(chǎn)結(jié)果甘特圖（圖5）可知，該組排產(chǎn)方案中，零件完工時(shí)間為14 h，全部零件在規(guī)定時(shí)間內(nèi)完成加工，且較規(guī)定完成時(shí)間提前2 h完成加工任務(wù)，機(jī)床綜合負(fù)載率達(dá)84%。其余加工設(shè)備利用率較第1種參數(shù)設(shè)置下的排產(chǎn)結(jié)果有了較為明顯提升，加工時(shí)間明顯縮短，加工設(shè)備得到了充分利用，排產(chǎn)結(jié)果較為理想。

圖5 第 2 種參數(shù)方案的排產(chǎn)甘特圖

第3種方案：種群規(guī)模為50，交叉概率為0.7，變異概率為0.4，迭代次數(shù)為1 000次。由排產(chǎn)結(jié)果甘特圖可知（圖6），該組排產(chǎn)方案中，零件最短加工完成時(shí)間為16 h，全部零件在規(guī)定時(shí)間內(nèi)完成加工，機(jī)床綜合負(fù)載率達(dá)73%，較第1種方案有所降低，排產(chǎn)結(jié)果較為緊湊。

圖6 第 3 種參數(shù)方案的排產(chǎn)甘特圖

3.2 實(shí)驗(yàn)結(jié)果對(duì)比分析

從作業(yè)完工時(shí)間、超期作業(yè)數(shù)、總超期時(shí)間、最大機(jī)床負(fù)載率和機(jī)床綜合負(fù)載率等5個(gè)方面，將3種參數(shù)方案的排產(chǎn)結(jié)果進(jìn)行對(duì)比，以評(píng)價(jià)排產(chǎn)算法的性能。實(shí)驗(yàn)結(jié)果對(duì)比如表2所示。

表2 實(shí)驗(yàn)結(jié)果對(duì)比

通過對(duì)比作業(yè)完工時(shí)間以及超期作業(yè)數(shù)，發(fā)現(xiàn)第1種排產(chǎn)方案存在超期現(xiàn)象，而第2種方案和第3種方案均可以在規(guī)定時(shí)間內(nèi)完成作業(yè)任務(wù)；通過對(duì)比機(jī)床負(fù)載率和機(jī)床綜合負(fù)載率，發(fā)現(xiàn)第2種方案下的機(jī)床綜合負(fù)載率都明顯高于第3種方案，且作業(yè)完工時(shí)間也較第3種方案短。綜合對(duì)比以上3種參數(shù)設(shè)置方案，認(rèn)為在第2種參數(shù)設(shè)置下得到的排產(chǎn)結(jié)果最為理想。

4 結(jié)語

本研究針對(duì)柔性制造系統(tǒng)的作業(yè)車間調(diào)度問題，采用遺傳算法進(jìn)行排產(chǎn)設(shè)計(jì)。通過對(duì)比3組不同參數(shù)，得到以下結(jié)論：通過調(diào)整算法中的種群規(guī)模、迭代次數(shù)和交叉變異概率等參數(shù)，發(fā)現(xiàn)增大種群規(guī)模和迭代次數(shù)，可以有效增加種群的多樣性，在一定程度上可以縮短作業(yè)完工時(shí)間，提高機(jī)床的負(fù)載率；通過調(diào)整交叉變異概率，發(fā)現(xiàn)作業(yè)完工時(shí)間以及機(jī)床負(fù)載率變化不大。通過對(duì)3組參數(shù)設(shè)置的運(yùn)行結(jié)果對(duì)比發(fā)現(xiàn)，第1組參數(shù)運(yùn)行結(jié)果存在超期現(xiàn)象，第2組參數(shù)運(yùn)行結(jié)果提前完成作業(yè)任務(wù)且機(jī)床負(fù)載率較高，第3組參數(shù)運(yùn)行結(jié)果為準(zhǔn)時(shí)完成作業(yè)任務(wù)，但機(jī)床利用率不夠高。因此通過對(duì)比上述3種參數(shù)設(shè)置方案，發(fā)現(xiàn)在第2組參數(shù)設(shè)置下得到的排產(chǎn)結(jié)果較為理想，可為后續(xù)基于遺傳算法的多目標(biāo)優(yōu)化排產(chǎn)算法的參數(shù)設(shè)置提供參考思路。后續(xù)研究可以通過改進(jìn)算法使作業(yè)盡量緊湊地排列在各個(gè)加工設(shè)備上，從而提高機(jī)床負(fù)載率，縮短作業(yè)完工時(shí)間，以期為FMS系統(tǒng)排產(chǎn)算法的智能化設(shè)計(jì)提供實(shí)踐參考。