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

軒 華 王 晶 張慧賢 李 冰

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

0 引 言

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

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

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

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

1 問題描述與建模

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

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

(1)

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

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

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

3) 目標函數。以最小化總加權完工時間為目標：

(2)

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

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上加工被占用工件數不能超過工序p可利用的機器總數。

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

2.1 基于啟發式規則初始化種群

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

初始化種群，采用啟發式規則(Heuristic Rules, HR)和隨機產生程序相結合的方式。基于五種啟發式規則HRl(l=1,2，…，5)產生解集{Ω1,Ω2,Ω3,Ω4,Ω5}，30%的初始種群從解集{Ω1,Ω2,Ω3,Ω4,Ω5}中均勻重復選取，剩余的70%個體采用隨機生成的方法，從而構成最終的初始種群。其中啟發式規則設計如下：

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

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

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

2.2 適應度函數及選擇

2.3 自適應交叉與變異算子

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

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

圖1 兩點倒置變異

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

(8)

(9)

設置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解的鄰域中繼續尋優。鄰域解由交換GA解染色體的兩個基因位產生，將染色體上第k(k=1,2,…,n-1)個位置的基因分別與第k+1,k+2,…,n位置的基因交換，將得到的適應度值最大的染色體對應的序列作為最佳鄰域解。

2.5 算法流程

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

圖2 HR-AHGA流程

3 算例實驗及實驗分析

3.1 算例實驗

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

表1 算例數據

圖3 算例甘特圖

因此，最終的總加權完工時間為：

3.2 算法測試

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

表2 參數設置

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

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

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

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

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

表3 兩種算法的結果比對

續表3

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

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

表4 不同規模問題的平均改進率

4 結 語

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

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