多品種小批量模式下離散制造車間調度問題研究

唐紅濤，楊 源，聞 婧

(1.武漢理工大學 機電工程學院，湖北 武漢 430070；2.湖北省數字制造重點實驗室，湖北 武漢 430070)

離散制造是現代制造的重要組成部分，也是國民經濟的重要支柱。離散制造企業(yè)大多采用面向訂單生產(make-to-order，MTO)的經營模式，這使得離散制造具備多品種、小批量的特點，并且各訂單之間的技術標準不同，導致無法成批生產，離散制造車間的生產管控更為復雜[1-2]，研究離散制造車間的生產調度問題對提高國家整體的制造水平有著重要意義。

國內外學者對以作業(yè)車間和流水車間為代表的離散制造車間生產調度問題展開了大量研究，取得了較為豐碩的成果[3-5]。Qiao[6]等針對離散制造車間高污染問題，建立了以最小化生產總成本和碳排放量為目標的生產調度模型，并使用改進的遺傳算法求解該問題。宋昌興[7]等研究了準備時間不確定的混合流水車間調度問題，建立了一個以最小化總拖期和制造期的多目標優(yōu)化模型，針對模型特點，基于NEH(nawaz ensore ham)-Pareto對傳統的模擬退火算法進行改進，最后的仿真實驗證明了算法的優(yōu)越性。

車間調度問題屬于典型的NP(nondeterninistic polynomin)-Hard問題[8]，而多品種模式下的柔性流水車間調度問題是在流水車間的基礎上考慮的多品種生產特性，故其仍然屬于NP-Hard問題范疇。諸如遺傳算法(genetic algorithm, GA)[9]、粒子群算法(partical swarm optimization, PSO)[10]、灰狼算法、蛙跳算法[11]等智能優(yōu)化算法等具備較快的求解速度，常被用于車間調度問題。特別地，候鳥優(yōu)化算法(migrating birds optimization algorithm，MBO)是一種新興的群智能優(yōu)化算法，其具備參數少，求解質量高等特點，近年來也被逐漸地被運用于求解車間調度問題。

大多數參考文獻將多品種-小批量模式下的調度問題處理為批調度問題，將同一類產品作為一個整體或者看作是一個工件進行批量調度，其本質上仍然屬于單件調度問題，不能實現更為精細化的調度方案。因此，筆者以柔性流水車間為研究對象，建立了一個多品種小批量模式下的生產調度模型，針對該模型的特點，設計了一種改進的候鳥優(yōu)化算法求解該模型，并構建了多組適用于多品種小批量模式下的混合流水車間調度問題的測試算例，通過與多個算法對比，驗證了改進的候鳥算法的高效性。

1 問題描述及模型構建

1.1 問題描述

以離散制造車間的典型代表柔性流水車間為例，多品種模式下的柔性流水車間調度問題(multi-variable flexible flow-shop scheduling problem，MFFSP)可描述為：車間需生產I種類型的產品，每類產品的生產批量為Ni，每件產品互不影響，所有產品都需要經過n個加工階段的處理，每個加工階段至少有一臺并行加工的設備可供選擇，每臺設備的加工時間不完全相同。MFFSP的目標為：為每件產品安排合適的設備并確定所有產品在設備上的加工順序以及對應的開工和完工時間，使得某個調度指標如總完工時間、設備負載率等最小等。

所研究的多品種模式下柔性流水車間調度問題主要解決以下兩個問題：①為每件產品分配加工設備；②確定每件產品的開工時間和完工時間。

為便于研究，筆者基于如下假設構建數學模型：

(1)在0時刻，所有的產品和設備均可用；

(2)產品投入生產不會被中止；

(3)同一時刻，一臺設備只能加工一件產品；

(4)同一時刻，任一產品只能被一臺設備加工；

(5)所有產品均有相同的工藝路線；

(6)不考慮設備故障、物料短缺等意外事件；

(7)所有產品的加工時間已知且固定，忽略各道工序間的運輸時間。

1.2 模型構建

1.2.1Y 符號與參數

I：產品的類型數量；

i,s：產品的類型編號，i,s∈[1,I];

Ni：第i類產品的工件總數量；

Ns：第s類產品的工件總數量；

j,t：工件標號，j∈[1,Ni]，t∈[1,Ns];

pij：產品種類i中的第j個工件;

n：產品的加工階段總數，即產品的最后一道工序編號;

k：工件的加工階段編號，k=1,2,…,n;

Mk：第k階段的設備數量;

mkl：加工第k階段的設備中的第l臺設備，l=1,2,…,Mk;

Qkl：設備mkl所加工的工件數量；

R：一個無窮大的正數;

Cij：工件pij的完工時間;

Cmax：所有工件的完工時間最大者。

1.2.2 決策變量

1.2.3 目標函數

minCmax=max{Cij} ?i,j

(1)

(2)

(3)

1.2.4 約束條件

(4)

k∈[1,n];l∈[1,Mk]

(5)

j∈[1,Ni];t∈[1,Ns];k∈[1,n]

(6)

j∈[1,Ni];t∈[1,Ns];k∈[1,n]

(7)

(8)

(9)

式(4)為每個工件的每個加工階段只能選擇一臺設備進行加工；式(5)為一個工件在一臺設備上只允許加工一次；式(6)和式(7)為同一階段不同工件存在先后加工順序次序約束；式(8)為同一工件不同階段存在先后順序約束；(9)為決策變量的取值范圍。

2 改進候鳥算法求解調度模型

2.1 基本候鳥算法簡介

候鳥算法MBO是由Duman于2012年提出的一種群智能算法，適用于諸如車間調度等離散優(yōu)化問題，該算法的靈感源于候鳥遷徙行為。MBO算法包含種群初始化、領飛鳥進化、跟飛鳥進化、領飛鳥更新4個步驟，種群初始化形成V形隊列，處于隊列最前端的領飛鳥對自身執(zhí)行鄰域搜索完成進化，左、右兩隊列前端的兩只跟飛鳥除了對自身進行鄰域搜索外還會保留來自領飛鳥的鄰域解，這有利于增強算法的全局搜索能力，如此循環(huán)多次后，從左右兩個隊列中隨機選取一只跟飛鳥替代領飛鳥，原來的領飛鳥放至隊列的尾部，循環(huán)迭代多次完成整個算法的流程。

2.2 編碼與解碼

筆者采用基于產品類別編號的單層編碼方式，如X=[2,3,2,3,1]表示工件第一個階段的加工順序，X是由產品類別編號組成的一個序列，其元素出現的次序為該類產品的工件編號，如X序列中處于位序3上的元素2第2次出現，表示第2類產品的第2個工件(用P22表示)，X序列對應的工件加工順序(第一個階段)為：P21-P31-P22-P32-P11。

上述編碼方案相對于雙層編碼方式而言，解空間減少一半且能解決多品種工件排序問題，但其僅表示工件第一個階段的加工順序，后續(xù)階段的工件排序以及設備分配需要通過解碼機制獲取，本文采用的解碼機制如下：

但是，EPC總包模式也不是完美的。智慧物流園區(qū)建設不同于傳統的園區(qū)信息化建設。首先，智慧物流園區(qū)更加強調的是站在園區(qū)的頂層視角，統籌考慮園區(qū)信息化發(fā)展需求和推進路徑，而不是孤立狹隘的建設一個個項目；其次，園區(qū)的信息化建設僅僅是智慧物流園區(qū)建設工作的一部分，建設完成后不等于能夠用好，要能夠讓智慧物流園區(qū)可持續(xù)的運轉起來，建設的項目能夠產生預期以及持續(xù)的效益，這才是智慧物流園區(qū)發(fā)展的最終目標。

(1)后續(xù)階段的工件排序。對于后續(xù)加工階段(k≥2)，工件排序采用先到先加工(first in first out, FIFO)規(guī)則，即上一階段中，工件完工時間更短者優(yōu)先安排加工，若存在多個工件可供選擇，從中隨機選取一個工件優(yōu)先安排加工。

(2)設備分配規(guī)則。設備分配采用最早完工優(yōu)先(the earliest completion time first, ECTF)規(guī)則，首先通過上述編碼序列X可解碼得到工件的加工順序，按照該順序依次為工件分配設備，工件優(yōu)先選擇能更早完工的設備，當存在多臺設備可供選擇時，優(yōu)先選擇加工時間最短的設備，若存在多臺加工時間相同的設備，則隨機選擇。

2.3 基于反向學習的種群初始化

(10)

式中：xmin、xmax為X序列的上界與下界。

基于反向學習和隨機的種群初始化步驟為：

步驟1隨機生成種群規(guī)模為N的初始種群Pop；

步驟2從初始種群Pop中隨機選取[N/2]([·]表示向上取整)個個體構成子種群Pop1，剩余的種群Pop2，按照式(10)對Pop1種群生成反向種群Pop3；

步驟3若反向序列所表示的解優(yōu)于當前解，則替換，否則保留至種群Pop3；

步驟4合并Pop2與Pop3以構成新的種群。

2.4 鄰域結構

領飛鳥進化與跟飛鳥進化均依賴于個體自身產生的鄰域解，因此設計合理的鄰域結構是MBO算法的關鍵步驟。對于車間調度問題，基于交換和插入操作的鄰域結構較為有效，為進一步提高MBO算法的效率，對交換和插入操作進行改進，提出了最優(yōu)交換和最優(yōu)插入操作。

(1)最優(yōu)交換操作。以n維度序列X={xi,1≤i≤n}為例，序列X為當前解，從X中隨機選取一個位置r(1≤r≤n)，按照從左到右的順序，將元素xr與其余n-1個位置的元素依次交換，比較交換后的鄰域解與當前解的優(yōu)劣，若優(yōu)于當前解，則替換當前解并終止交換操作。

(2)最優(yōu)插入操作。同樣以序列X為例，從X中隨機選取一個位置s(1≤s≤n)，將元素xs按從左到右的順序插入到其余位置處，被插入位置及其后面所有元素均先后移一位，顯然可以產生n-1個鄰域解，當鄰域解優(yōu)于當前解時，則替換當前解并終止插入操作。

領飛鳥與跟飛鳥均使用最優(yōu)交換操作和最優(yōu)插入操作完成進化，進化過程中最優(yōu)交換和最優(yōu)插入執(zhí)行機率各占一半。

2.5 局部搜索策略

為避免MBO算法陷入局部最優(yōu)，對候鳥個體進行局部搜索，基于4種鄰域結構對候鳥個體進行變領域搜索，4種鄰域結構分別為：

(1)隨機交換。從當前候鳥序列隨機選取兩個不同的位置，交換兩個位置的元素形成新的鄰域解。

(2)隨機插入。從當前候鳥序列中隨機選取一個位置，將該位置元素隨機插入到其他任意一個位置形成新的鄰域解。

(3)逆序操作。從當前候鳥序列中任意選取兩個位置，將這兩個位置之間的元素進行逆序操作，從而獲得新的鄰域解。

(4)打亂互換。從當前候鳥序列中隨機選取多個位置，隨機打亂這些位置上的元素順序以獲得新的領域解。

設集合C為包含上述4種鄰域結構的集合，i為指向C中鄰域結構的索引，X為候鳥個體，Ci(X)為使用集合C中的第i個鄰域結構對個體X產生鄰域解，基于上述4種鄰域結構的變鄰域搜索步驟如下：

步驟1初始化索引i，令i=1;

步驟2獲取新的鄰域解X*，X*=Ci(X)，若X*優(yōu)于X，則用X*替換X，否則，令i=i+1；

步驟3若i≤4，執(zhí)行步驟2，否則，結束變領域搜索，輸出解X。

2.6 改進候鳥算法流程

在改進候鳥算法中各變量的含義如下：I為算法總迭代次數；i為當前迭代次數；Pop為候鳥種群規(guī)模；N為候鳥產生的領域解數量；g為領飛鳥與跟飛鳥巡回次數索引；G為最大巡回次數；x為領飛鳥未使用的領域解；l為左邊隊列跟飛鳥的索引；r為右邊隊列跟飛鳥的索引。

步驟1初始化算法參數(I，Pop，N，G)，令g=1，i=1；

步驟2使用反向學習策略完成種群初始化，種群中的第一只候鳥為領飛鳥，種群中第2只候鳥至第(P-1)/2只候鳥構成左隊列，并令l=2，種群中第(P-1)/2+1只候鳥至第P只候鳥構成右隊列，并令r=(P-1)/2+1；

步驟3領飛鳥進化。使用2.4中的鄰域結構對領飛鳥生成N個鄰域解，若最優(yōu)的鄰域解優(yōu)于領飛鳥，則替換領飛鳥，并將領飛鳥未使用的x個鄰域解分別傳遞至第l和第r只跟飛鳥；

步驟4若l≤(P-1)/2，則使用2.4中的鄰域結構對第l只跟飛鳥(左隊列)產生N-x個鄰域解，若最優(yōu)的鄰域解優(yōu)于當前跟飛鳥，則替換該跟飛鳥，并將未使用的鄰域解傳遞給第l+1只跟飛鳥，令l=l+1，并繼續(xù)執(zhí)行步驟4；

步驟5若r≤P，則使用2.4中的鄰域結構對第r只跟飛鳥產生N-x個鄰域解，若最優(yōu)鄰域解優(yōu)于當前跟飛鳥，則替換該跟飛鳥，并將未使用的鄰域解傳遞給第r+1只跟飛鳥，令r=r+1且g=g+1，并繼續(xù)執(zhí)行步驟5；

步驟6若g≤G，跳轉至步驟2，否則執(zhí)行步驟7；

步驟7對候鳥種群進行局部搜索；

步驟8隨機選擇左隊列或者右隊列中的第一只跟飛鳥替換領飛鳥，并將當前領飛鳥置于對應隊列的末端，令i=i+1；

步驟9若i>I，算法終止，否則，跳轉到步驟2。

3 仿真實驗

3.1 實驗設計

為驗證IMBO(improved migrating birds optimization)算法求解MFFSP模型的性能，將IMBO算法與遺傳算法(GA)、離散粒子群算法(discrete particle swarm optimization, DPSO)以及經典的MBO算法進行對比實驗，對比算法的參數均按照相應參考文獻建議值設置，筆者所提IMBO算法采用正交試驗法經過多次組合試驗獲得：候鳥種群規(guī)模P=60，最大迭代次數I=200，候鳥產生鄰域解數量N=5，傳至下一只候鳥的鄰域解數量x=2，候鳥進化最大巡回次數G=10。所有算法均采用上述編解碼方式，IMBO采用基于反向學習的種群初始化方式，其他算法均采用隨機初始化方式。使用Matlab 2016b軟件編寫，運行在Intel Core i7、CPU 2.9 GHz、RAM 8 GB、Window 10的64bit計算機上。同時為了保證實驗的公平性以及避免實驗結果的偶然性，每個算法獨立運行20次。

3.2 算例構建

筆者基于Benchmark算例集[4]構建適用于多品種小批量模式下的柔性混合流水車間調度問題測試算例，具體的構建參數如表1所示，產品類型數量分別為5、10、15和20，加工階段數分別為5、10、15，故可構建12個測試算例，算例的命名規(guī)則為“產品種類數-加工階段數”；階段數為5和15的測試算例采用參考文獻[4]中提出的c類設備布局(中間階段有2臺設備，其余階段均為3臺設備)，階段數為10的測試算例采用d類布局(所有階段均有3臺設備)，每類產品的生產數量xi為區(qū)間[1,5]上服從離散均勻分布的隨機數，加工時間為區(qū)間[10,20]上服從離散均勻分布的隨機數。

表1 算例構建參數

3.3 結果分析

基于上述構建的12個算例開展算法對比實驗，采用最優(yōu)值(Cbest)、最差值(Cworst)、平均值(AVG)以及相對誤差(RPD)4個指標對算法結果進行評價，式(11)為RPD的計算公式，其中，C0為當前算法運行20次的最優(yōu)值，C1為所有算法運行20次的最優(yōu)值，實驗結果如表2所示。

(11)

從表2可知，IMBO在最優(yōu)值方面取得了11個算例的最優(yōu)解，對應的RPD值均為0；在最差值方面取得了11個算例的最優(yōu)解，對應PRD值只有算例I5N10為1.15，其他算例均為0；在平均值方面取得了10個算例的最優(yōu)解，RPD值均為0，這證明了IMBO算法的可行性和穩(wěn)定性，MBO在尋優(yōu)能力上不及IMBO，這是因為所提出的IMBO增加了變鄰域局部搜索的原因，極大地提升了MBO的尋優(yōu)能力，GA算法和DPSO算法性能相差不大，但尋優(yōu)能力和穩(wěn)定性均遠落后于IMBO算法。圖1給出了算例“I10N15”的迭代曲線圖，顯然，IMBO算法的尋優(yōu)能力最強，其中的局部搜索極大避免了算法陷入局部最優(yōu)，其相對于其他3種算法而言，IMBO算法具有更快的收斂速度。

表2 算法對比結果

圖1 算例I10N15的迭代曲線圖

4 結論

筆者研究了多品種、小批量模式下的柔性流水車間調度問題，建立了以最小化最大完工時間為優(yōu)化目標的數學模型，針對多品種小批量的生產特點，對傳統的MBO算法進行改進，基于Benchmark算例集構建了12個適用于該模型的算例，并設計了對比實驗，證明了IMBO算法的有效性及高效性。