混合遺傳算法求解含機器可利用約束的HFSP

軒 華 王 晶 張慧賢 李 冰

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

0 引 言

帶機器可利用約束和阻塞的混合流水車間調(diào)度問題(Hybrid Flowshop Scheduling Problem with Machine Available Constraint and Blocking，HFSP-MACB)同時考慮了機器故障和機器阻塞。由于機器故障或維護等使機器在一定時間內(nèi)無法用于正常工作。在實際生產(chǎn)過程中，機器故障是常見的不確定因素，會對生產(chǎn)計劃和結(jié)果產(chǎn)生偏差，甚至可能會引起配送等環(huán)節(jié)的混亂。因此在制定生產(chǎn)計劃時考慮機器故障干擾，減少機器故障對調(diào)度性能的影響。此外，在相鄰生產(chǎn)階段的緩沖區(qū)能力有限或不存在，當工件完成前道工序的加工后，如不能進入緩沖區(qū)等待則需停留在加工它的機器上直至下游機器釋放，從而導致了該機器的阻塞。這類問題在工業(yè)生產(chǎn)中有著較廣泛的應用。例如，在船舶平面分段制造模式下，平面分段的重量和體積較大等導致難以儲存，考慮到經(jīng)濟性，工序之間一般不設(shè)置緩沖區(qū)，當前道工序的任務完成后，需要下道工序的工位釋放后才能繼續(xù)進行加工，此時就形成了阻塞。同時，分段從前道工序運送到后道工序的運輸時間不可忽略。因此，這就形成了考慮運輸時間的HFSP-MACB。Hall等[1]已證明當機器數(shù)多于兩臺時不考慮運輸時間的阻塞流水車間是強NP-hard，故所研究的帶運輸時間HFSP-MACB也是強NP-hard。

運輸時間有兩類，一類是與工件相關(guān)，即運輸時間取決于工件自身；另一類是工件無關(guān)的，即運輸時間由相鄰生產(chǎn)階段之間的距離決定。針對帶運輸考慮的兩階段HFSP，為最小化makespan，文獻[2]假定運輸時間取決于工件，每階段有多臺同構(gòu)并行機，提出了一種兩階段啟發(fā)式和一種分支定界精確方法；文獻[3]針對階段1含多臺批處理機而階段2有多臺離散機的情況，考慮與工件無關(guān)的運輸時間，提出一種混合多種啟發(fā)式規(guī)則的差分進化算法。針對帶運輸考慮的多階段HFSP，文獻[4]還考慮了可能返工時間、不同準備時間和預期順序相關(guān)調(diào)整時間，提出了一種增強入侵雜草優(yōu)化算法以最小化makespan；文獻[5]針對初始階段有串行批處理機的情況，提出了改進遺傳算法以最小化總加權(quán)完工時間；文獻[6]則針對可重入HFSP，提出了兩種拉格朗日松弛算法以最小化總加權(quán)完工時間。

為解決帶阻塞的混合流水車間makespan問題，在中間緩沖能力有限的條件下，文獻[7]提出了啟發(fā)式算法，該方法也可用于求解阻塞HFSP；文獻[8]以表面貼片技術(shù)線為背景，提出了一種精確算法和一種啟發(fā)式方法；文獻[9]提出了一種禁忌搜索算法。在無中間緩沖的條件下，文獻[10]提出了一種啟發(fā)式算法；文獻[11]基于禁忌搜索和優(yōu)先級規(guī)則提出一種方法；文獻[12]結(jié)合嵌套變鄰域搜索提出了一種memetic算法；文獻[13]提出了混合粒子群優(yōu)化算法；文獻[14]假定并行機為無關(guān)機，提出了一種改進離散布谷鳥搜索算法；文獻[15]假定每階段有不同加工速度的并行機，相鄰階段間由一個單爪機器人運送零件，每個零件在每個階段只能由指定機器集中的一臺進行加工，提出了基于模擬退火的求解方法；文獻[16]考慮了無關(guān)并行機和機器合格性約束，利用機器人卸載、運送和裝載零件，每個零件有釋放時間，其運輸時間取決于工件，基于蟻群優(yōu)化和遺傳算法提出了兩種超啟發(fā)式算法。

上述文獻均默認機器在所有時間連續(xù)可用，然而，這種假設(shè)在實際工業(yè)生產(chǎn)上并不成立。目前關(guān)于機器可用性與生產(chǎn)集成調(diào)度的研究多為單機[17-18]、并行機[18]、流水車間[19-20]和混合流水車間環(huán)境[21]。對于較為復雜的阻塞HFSP的研究較少，文獻[22]探討了兩階段阻塞HFSP，假設(shè)機器不能連續(xù)可用，提出了遺傳算法最小化makespan。但是缺乏關(guān)于同時考慮阻塞和機器可利用約束的研究。研究的目標多為makespan，而總加權(quán)完成時間問題有助于降低在制品庫存和加強工序間的時間銜接等。為此，本文以考慮運輸?shù)亩嚯A段HFSP-MACB的集成調(diào)度為研究對象，以最小化總加權(quán)完成時間為目標，建立基于故障時間窗的集成優(yōu)化模型，提出一種混合啟發(fā)式和局域搜索的自適應混合遺傳算法以有效求解該問題。

1 問題描述與建模

n個工件通過s個工序進行加工，至少存在某個工序p的同構(gòu)并行機數(shù)Mp≥2，一臺機器一次只能加工一個工件，一個工件一次只能在一臺機器上加工；工件在相鄰兩個工序之間傳送都需要運輸時間；相鄰兩個工序之間無中間緩存區(qū)；由于機器長時間加工導致磨損、老化等，機器有一定發(fā)生故障的概率，當機器發(fā)生故障時，對機器進行維修，維修期間機器無法用于工件加工。通常機器發(fā)生故障的準確時間是無法預知的，因此采用機器故障統(tǒng)計相關(guān)數(shù)據(jù)的概率分布代替，計算公式如下：

n∈{1,2，…,N},z∈{1,2，…,Z}

(1)

式中：Pn(z)表示機器n在時刻z出現(xiàn)故障的概率；Zn表示機器n的運行時間。

1) 已知參數(shù)。工件集為J(J=1,2,…,n)，j表示工件序號，n表示工件總數(shù)；工序序號為p，總加工工序為s；工序p的機器數(shù)為Mp，機器序號為m，總機器數(shù)為TM；工件j從工序p到p+1的運輸時間為Tj(p,p+1)；工件j在工序p的機器m上加工時間為Wjpm；Z表示計劃時間范圍，z為時間段序號，z∈{1,2，…，Z}；hj表示工件j的權(quán)重。

2) 決策變量。若工件j在工序p使用機器m加工，Xjpm值為1，否則為0；若工件j在時刻z正在工序p上加工或阻塞，Yjpz值為1，否則為0；時刻z第p道工序可用的機器數(shù)為apz；工件j在工序p的開始加工時間為bjp，完成加工時間為cjp；工件j的完工時間為Cj。

3) 目標函數(shù)。以最小化總加權(quán)完工時間為目標：

(2)

4) 工序優(yōu)先級約束。工序優(yōu)先級約束要求工件在每道工序只有在前一工序加工完成并運輸至后一工序，才可開始該工序的加工：

Tj(p,p+1)+cjp+1≤bj,p+1j∈J,p∈{1,2，…，s-1}

(3)

5) 機器能力約束。

(4)

p∈{1,2，…,s},z∈{1,2，…,Z}

(5)

式(4)表示工件在各工序只能在一臺機器上進行處理；式(5)表示機器能力約束要求z時刻在工序p上加工被占用工件數(shù)不能超過工序p可利用的機器總數(shù)。

6) 工序加工時間要求。工件j在第p道工序的加工時間表示為：

cjp=bjp+Wjpm-1j∈J,p∈{1,2，…，s},m∈{1,2，…,TM}

(6)

7) 機器占用時間約束。工件j在工序p上占用機器時間等于工件在p+1階段的開工時間減去在p階段的開工時間及工序p到p+1之間的運輸時間：

j∈J,p={1,2，…,s-1}

(7)

2 自適應混合遺傳算法

由于HFSP-MACB是強NP-hard問題，因此提出基于啟發(fā)式規(guī)則的自適應混合遺傳算法(Heuristic Rules Based Adaptive Hybrid Genetic Algorithm, HR-AHGA)求解上述模型。遺傳算法是基于生物進化原理提出的一種智能搜索算法，有較好的魯棒性，但容易陷入局部最優(yōu)。設(shè)計多種啟發(fā)式規(guī)則對初始種群進行改進，并采用自適應交叉和變異一定程度避免算法早熟。利用局域搜索 (Local Search, LS)對GA解的鄰域空間作進一步搜索，改善解的質(zhì)量。

2.1 基于啟發(fā)式規(guī)則初始化種群

采用自然數(shù)編碼方式，每個染色體為n個工件的排序，即μ={μ(1),μ(2),…,μ(n)}，其中μ(k)表示染色體上第k個位置工件的工件號，工件個數(shù)即為染色體長度。

初始化種群，采用啟發(fā)式規(guī)則(Heuristic Rules, HR)和隨機產(chǎn)生程序相結(jié)合的方式?；谖宸N啟發(fā)式規(guī)則HRl(l=1,2，…，5)產(chǎn)生解集{Ω1,Ω2,Ω3,Ω4,Ω5}，30%的初始種群從解集{Ω1,Ω2,Ω3,Ω4,Ω5}中均勻重復選取，剩余的70%個體采用隨機生成的方法，從而構(gòu)成最終的初始種群。其中啟發(fā)式規(guī)則設(shè)計如下：

(1) 權(quán)重越大越優(yōu)先加工規(guī)則HR1。將工件按權(quán)重Wh的降序排序，依次將工件分配到可利用的機器上，得到可行解Ω1。

(4) 總阻塞時間越小越優(yōu)先規(guī)則HR4。隨機產(chǎn)生多個可行解，計算相應的總阻塞時間，得到最小阻塞時間對應的可行解Ω4。

(5) 最大完工時間越小越優(yōu)先規(guī)則HR5。對若干個隨機生成的可行解分別計算最大完工時間，得到最大完工時間最小的可行解Ω5。

2.2 適應度函數(shù)及選擇

2.3 自適應交叉與變異算子

交叉算子采用單點交叉的方式，將選擇后的染色體順序打亂，取相鄰的兩個父代個體配成一組，隨機選擇一個基因位，交換該基因位之前的染色體片段，形成新的子代染色體，若交換后出現(xiàn)基因重復，則修正重復點，從而形成兩個可行的子代。

變異算子有利于提高種群的多樣性，防止算法陷入早熟。采用兩點倒置變異，隨機選擇染色體上的兩個基因位并交換這兩個基因，形成新的子代，如圖1所示。

圖1 兩點倒置變異

傳統(tǒng)GA的交叉和變異概率通常是個常數(shù)，而遺傳進化本身是一個動態(tài)的過程，這種設(shè)定可能不利于有效求解。因此，設(shè)計了隨迭代進程動態(tài)變化的交叉概率pc和變異概率pm，來增強GA的搜索能力及更新速度。

(8)

(9)

設(shè)置pcmin=0.35，pmmax=0.15。

當1≤g≤G/4時，pmmin=0.006，pcmax=0.65；

當G/4≤g≤3G/4時，pmmin=0.045，pcmmax=0.5；

當3G/4≤g≤G時，pmnin=0.09，pcmax=0.3。

2.4 應用LS更新GA解

為進一步提高GA當前解，引入局域搜索，在GA解的鄰域中繼續(xù)尋優(yōu)。鄰域解由交換GA解染色體的兩個基因位產(chǎn)生，將染色體上第k(k=1,2,…,n-1)個位置的基因分別與第k+1,k+2,…,n位置的基因交換，將得到的適應度值最大的染色體對應的序列作為最佳鄰域解。

2.5 算法流程

基于上述描述，得到HR-AHGA的流程，如圖2所示。

圖2 HR-AHGA流程

3 算例實驗及實驗分析

3.1 算例實驗

設(shè)工件數(shù)n=7，工序數(shù)s=3，每道工序上的并行機數(shù)分別為2、3、2。工件加工時間Wjpm、權(quán)重hj和相鄰工序之間的運輸時間Tj(p,p+1)如表1所示，運行HR-AHGA得到最佳調(diào)度方案為1→2→4→5→7→6→3，調(diào)度解如圖3所示，其中：M表示機器；J表示工件，b表示相應工件在機器上阻塞。

表1 算例數(shù)據(jù)

圖3 算例甘特圖

因此，最終的總加權(quán)完工時間為：

3.2 算法測試

為了驗證算法的有效性，對HR-AHGA進行編譯，并與傳統(tǒng)GA進行比對，兩種算法均在CPU為2.60 GHz，內(nèi)存為4.00 GB的Lenovo G480微機的MATLAB R2014a上實現(xiàn)。種群規(guī)模PopSize設(shè)為80，最大迭代次數(shù)G設(shè)為160。通過對不同遺傳參數(shù)設(shè)置的仿真測試，設(shè)置傳統(tǒng)GA的交叉概率設(shè)為0.8，變異概率設(shè)為0.06。實驗場景設(shè)置如表2所示。

表2 參數(shù)設(shè)置

算法性能通過改進率L和計算時間CPU衡量，其中目標值改進率L[9,12]和時間增加率R定義為：

L=(TWCGA-TWCHR-AHGA)/TWCHR-AHGA×100%

R=(CPUHR-AHGA-CPUGA)/CPUGA×100%

TWC表示由相應算法得到的目標值，CPU為計算機運行時間。

每種組合{n,s,Mp}隨機產(chǎn)生9個實例，共測試6×2×2×9=216組實驗。實驗結(jié)果如表3所示，表中數(shù)據(jù)均為同一規(guī)模的9組實例的均值(除最后一行)。

表3 兩種算法的結(jié)果比對

續(xù)表3

對于不同規(guī)模問題，GA和HR-AHGA在相同迭代次數(shù)內(nèi)得到的平均目標值分別為308.65和252.49，與GA相比，HR-AHGA平均運行時間僅增加了1.96%，由HR-AHGA得到的平均目標值改進了16.81%。中小規(guī)模(n={30, 60, 90})和大規(guī)模(n={150, 200, 300})問題的平均改進率分別為7.55%和26.07%，這說明了HR-AHGA相對于GA，在求解大規(guī)模問題時改進效果更好。

表4表明了不同工件規(guī)模的平均改進率，工件規(guī)模為30時，平均改進率為1.85%，當工件規(guī)模達到300時，改進率達到30.49%；而平均增加運行時間僅從0.35%增加到2.93%?？梢钥闯?，隨著工件規(guī)模增大，HR-AHGA相對于GA的改進率也逐漸增大。因此，整體來看，HR-AHGA在合理的計算時間內(nèi)能夠得到更好的近優(yōu)解，在求解大規(guī)模問題時更顯著。此外，本文測試問題規(guī)模為n={30,60,90,150,200,300}，s={3,4}，Mp={3,4}，根據(jù)測試結(jié)果，采用HR-AHGA求解300個工件4個階段的各實例中所需的最長運行時間為506.25 s ，能夠在較短時間內(nèi)求出近優(yōu)解。根據(jù)表4，相比GA，引入LS后的HR-AHGA求解所有規(guī)模問題的平均時間增加率為1.96%，故該算法也可以求解其他甚至更大規(guī)模算例。

表4 不同規(guī)模問題的平均改進率

4 結(jié) 語

本文考慮了機器故障、無緩存區(qū)、運輸時間等實際生產(chǎn)約束條件的混合流水車間調(diào)度問題，以最小化總加權(quán)完工時間為目標，建立了MIP模型，提出一種自適應混合遺傳算法求解帶運輸時間的HFSP-MACB。設(shè)計了五種啟發(fā)式規(guī)則改進初始種群，一定程度上彌補了不確定性規(guī)則搜索的不足；引入LS對GA產(chǎn)生的解的鄰域空間進一步地搜索來尋優(yōu)。對不同規(guī)模問題的仿真測試證明HR-AHGA的可行性和有效性，相比傳統(tǒng)遺傳算法求解效率更好，在求解大規(guī)模問題時，本文算法更具優(yōu)越性，對于實際生產(chǎn)效率的提高有很大意義。

本文考慮中間無緩存區(qū)的混合流水車間問題，可將本文模型推廣至有限緩存區(qū)調(diào)度問題。采用LS規(guī)則對GA解進行改進的策略，進一步研究可以采用其他啟發(fā)式算法對GA改進或者將LS嵌入GA迭代過程中，或者采用其他超啟發(fā)式算法進行求解，如粒子群算法、螢火蟲算法等。