改進的自適應NSGA-II求解多目標流水車間調度問題

張 偉

(福建船政交通職業學院通用航空產業學院，福建福州 350007)

0 引言

針對流水車間調度問題，調度問題學者Johnson[1]起先于1954年發表行之有效的算法，至此許多學者紛紛加入研究流水車間調度問題行列，取得了大量的研究成果.其中多是關注解決單目標問題，即構建最大完工時間最小為優化目標模型[2,3]，除此之外，還有最小化最大延遲時間[4]和總流程時間[5]等，它們是衡量生產經濟效益、關乎調度成本的重要指標.可是面對競爭越來越激烈的產品制造行業，經營者往往要思量兩個及以上優化目標，而這些目標之間存在矛盾關系.從而，在流水車間調度中琢磨其多目標問題就顯得越有工程價值.

宋存利[3]設計了一種改進貪婪遺傳算法，應用逆序解碼和正序解碼、貪婪交叉算子、貪婪變異算子，用于改善最大完成時間目標，使其達到最小.王宇等[6]構思了實數編碼、差分進化變異、混合采樣的多目標差分進化算法，用以最小化最大拖期和最大完工時間.張聞強等[7]提出一種快速多目標混合進化算法，用以解決雙目標的流水車間調度問題，為使最大完工時間和總流經時間最小并取得最佳.羅哲[8]設想了一種混合遺傳算法，通過灰熵并行關聯度作為算法適應值挑選子代，并建立Pareto外部檔案、使用Pareto排序和擁擠距離計算，用以在流水車間調度問題中優化最大拖期時間、總流程時間和最大完成時間三個目標.

基于以上文獻分析，許多學者探究的重點是兩個目標的優化問題，也有少部分關注三個目標優化問題的鉆研，并且研究成果多數是通過多目標進化算法求得.因此，本文按照某企業流水車間的一條實際生產線調度環境，綜合考慮了最大完工時間、總拖期時間和總流程時間最小三個目標并為此構建調度模型，通過帶有自適應參數調節改進的NSGA-II算法在調度解空間找尋Pareto解集，將數據進行加權處理挑選出中意的調度方案，表明該算法在解決多目標流水車間調度問題上是可行的、有效的.

1 流水車間調度問題描述和數學模型構建

1.1 流水車間調度問題描述

流水車間調度問題通常描述如下：n(w1,w2,…,wn)個產品在m(M1,M2,…,Mm)臺機器上進行生產，每個產品都要進行p道工序的生產，每臺設備分配不同的工序進行生產.第i個產品的第j道工序表示為Rij，第u個產品的第j道工序表示為Ruj，n個產品的p道工序具有一樣的加工路徑，即不同產品的相同工序是在相同的機器上生產，表示為M(Rij)=M(Ruj)，其中i≠u，i，u=1,…,n；j=1,…,p.Rij被分配在設備Mg(g=1,2,…,m)上進行生產，則其生產時間表示為Tijg.在一般流水車間調度問題中，一臺設備被唯一分配一道工序進行生產，生產設備不能挑選，即p=m.已知每臺設備上生產產品的的時間，要求明確設備上生產產品的次序，其目的是獲得多目標函數的Pareto前沿.而且流水車間調度問題又符合普遍性的約束要求與設想[9].

1.2 數學模型構建

Cw11=Tw11

(1)

Cw1g=Cw1g-1+Tw1g;g=2,...,m

(2)

Cwi1=Cwi-11+Twi1;i=2,...,n

(3)

Cwig=max(Cwi-1g;Cwig-1)+Twig;i=2,...,n;g=2,...,m

(4)

鑒于流水車間的生產效率最大、資源配置合理和庫存最小以及符合用戶對產品訂單的時間預期，本文考慮以使最大完工時間f1=Cmax、總流程時間f2=Ctotal和總拖期時間f3=Detotal最小的優化目標，即f=min(f1,f2,f3).其中：

(1)最大完工時間相應的目標函數Cmax：

Cmax=max(Cwim|i∈1,2,...,n)

(5)

(2)總流程時間相應的目標函數Ctotal：

(6)

(3)總拖期時間相應的目標函數Detotal：

(7)

其中：

2 自適應參數的NSGA-II算法設計

關于多目標優化問題的求解，呈現出許多多目標優化算法，有模擬退火算法、粒子群優化算法、遺傳算法等.模擬退火算法采取冷卻表進行探尋，模擬物理學中金屬的平緩冷卻過程規律，通常選取變權重措施開展目標函數加權組合，其實現過程慢且收斂能力尚待加強.粒子群優化算法采取類似于蜜蜂采蜜、螞蟻覓食、鳥群捕食等行為的原理，經由粒子在探尋空間追隨最佳粒子進行探尋，如果該粒子趕上粒子群目前的最佳粒子，出現種群多樣性會丟失、早熟問題，同時如果粒子群的目前最佳值和一個粒子的目前位置與該粒子的目前最佳值一致，致使算法無法收斂.多目標遺傳算法(MOGA)在Pareto支配等級基礎上可以獲取分布勻稱的適應度，其采用適應度共享方法可以實現在選擇壓力適合的條件下維系整個種群的適應度為常數，然而由Pareto支配關系確定等級的方法可能使選擇壓力較大而導致非成熟收斂，如果一樣的目標函數值對應于多個不同的非支配解，MOGA不易找出多個解.Pareto小生境遺傳算法通過非支配關系進行聯賽選擇，且通過小生境技術來共享適應值維系種群多樣性，其可以得到不差的Pareto前沿，缺點是比較集大小的揀選與小生境半徑揀選沒有一個一致的規范.而帶精英策略的快速非支配排序遺傳算法(NSGA-II)[10]選擇一種快速非支配排序方法，使計算復雜度減少；利用擁擠距離和擁擠比較算子獲取勻稱的Pareto前沿，用于維系種群多樣性；提出卓越解保存準則，將父代中卓越解保存，從而優化越恰當.本文通過NSGA-II算法來處理第1方面提出的多目標流水車間調度問題，采用自適應參數與NSGA-II算法結合以達到動態調節交叉、變異算子的目的，確保不丟失最佳解.

2.1 編碼

在流水車間調度問題中，產品在機器上加工路徑相同，不同工序在不同的機器上進行加工，因而算法選擇采用基于產品的編碼方式，即n個產品排列組合生成染色體，每條染色體中產品的先后次序代表一種調度信息.例如，7個產品在流水生產線上制造加工，假設一組產品的排列是w7、w1、w2、w3、w4、w6、w5，就體現一種調度策略W=7，1，2，3，4，6，5.

2.2 Pareto排序

對種群I進行非支配排序是為了獲取種群中支配個體i的非支配數ni和被個體i支配的支配集Pi.其詳細實施過程如下：

國企面臨的另一重大沖擊來自鄉鎮企業。當時，鄉鎮企業在江蘇南部和山東的膠東半島迅速發展起來，鄉鎮企業因為機制靈活在競爭中明顯優于國有企業，并出現了“星期天工程師”現象：國有企業的技術人員，星期天到附近鄉鎮企業“走穴”，進行技術支持。

(1)對比種群中的兩個個體i與j，當i好于j時，Pi=Pi∪{j}；當i差于j時，ni=ni+1；如果ni=0，則

Frank=Frank∪{i}.

(2)Pt是目前集合Frank中的每個個體t所支配的個體集合，針對Pt中保存的每個個體q，執行nq=nq-1步驟，若nq=0，則R=R∪{q}.

(3)非劣等級rank=1，即Frank=F1是第一非劣等級的個體集合，循環執行rank=rank+1，R=Frank步驟，直至種群中全部個體被非劣排序為止.

2.3 擁擠距離

為了維護種群多樣性，算法定義擁擠距離來確保Pareto解集可以約束到一個分散勻稱的Pareto前沿.其計算公式為：

(8)

其中：d(k)distance是第k個個體的擁擠距離，f(k+1).e、f(k-1).e分別是第(k+1)、(k-1)個個體第e個目標分量的函數值，femax、femin分別是第e個目標分量的函數值最大值與最小值.

2.4 選擇

選擇使種群演變朝向Pareto最佳解的方位逼近，以確保Pareto前沿勻稱分散.算法采用二元聯賽選擇，其原理為隨便遴選兩個個體i與j進行比較，選擇最優的個體進入下一代種群，鑒別個體i好于j的標準如下：非劣等級rankj>ranki；或ranki=rankj，而擁擠距離d(i)distance>d(j)distance.

2.5 交叉

交叉是種群演變進化的核心算子，它可以擴大算法搜索新空間的可能性，但也得考慮演變的約束性問題.交叉算子總是期盼能獲取一些有效的新個體樣式，卻又能較大程度地保護代表卓越基因的卓越樣式.本文選用部分匹配交叉，其整體探尋成效較優，不輕易陷進局部最優，確保經過遺傳最佳樣式能夠最大程度地得到保留.如圖1所示，依據I中兩個父代個體g1、g2動態獲取的兩個交叉點以得到一個匹配段，比如3、5是選定的位置；由選定的位置之間所構成的匹配段確定部分映射關系為4-6、2-5、7-2，將兩個交叉點之間的染色體部分交換，得到如II中g1，、g2，；根據匹配段交叉點之間基因映射關系，將g1，、g2，交換區域之外的一樣的基因一一交換，從而獲得III中子代個體h1、h2.

圖1 部分匹配交叉Fig.1 Partial matching crossover

2.6 變異

變異實現種群演變收斂進程中防止陷入局部最優功能，可以增加種群的多樣性.本文選用對換操作變異，通過動態方式在一個個體上生成兩個變異位置，將這兩個變異位置相應的染色體編碼互換.比如2、6是變異的位置，圖2所示為其操作過程.

圖2 對換變異Fig.2 Swapping mutation

2.7 自適應參數調整策略

采用基于進化階段的自適應方法作為個體交叉率與變異率的調整方法[11].第一，要明確劃分進化階段，在同一進化階段中進行個體交叉率與變異率設置，在不同進化階段中設置交叉率和變異與基于進化階段的自適應方法一樣.當進化代數增加時，不同階段個體交叉率與變異率呈線性下降走向，直至它在數值上與下一階段的初始交叉率與變異率相等為止.第二，為了確保在進化后期個體也還有一定的幾率參與進化，該方法中的交叉率與變異率會伴隨進化代數的增加逼近一個趨近于0但不等于0的值.自適應交叉率與變異率的模型的兩個部分如下：

(1)當非支配解個數小于10時，個體交叉率與變異率的模型為：

(9)

(10)

(2)當非支配解的個數不小于10時，該情況下的個體交叉率模型不變，而變異率的模型為：

(11)

其中：Pc是個體的交叉率，Pm是個體的變異率，N是算法的最大迭代次數，L是個體的編碼長度.N1=αN，N2=(1-α)N.β是進化后期階段交叉率與變異率的調節參數，β∈(0,1].0～N1為算法的進化初期階段，N1～N2為算法的進化中期階段，N2～N為算法的進化后期階段.

2.8 精英保留策略

為了防止父種群中卓越的個體流失，而直接將其放到子種群中，算法引入精英保留策略，使種群演變收斂得到保證.算法執行的過程是：首先生成復合種群G，它是由父代種群P與子代種群Q組合形成；然后將快速非支配排序和擁擠距離計算應用到復合種群G中；最后選取卓越的個體形成新一代種群H，這個過程在復合種群G中進行.算法的詳細過程如圖3所示.

圖3 改進的自適應NSGA-II流程Fig.3 Improved adaptive NSGA-II process

3 實例

3.1 基礎數據

某企業有一條流水線采用8臺設備生產7件產品.鑒于流水車間的生產效率最大、資源配置合理和庫存最小以及符合用戶對產品訂單的時間預期，需要考慮以使最大完工時間、總流程時間和總拖期時間最小的優化目標，從而使產品產能生產最大化，提升經濟收益.已知每個產品的交貨期如表1所示，每個產品每道工序的生產時間如表2所示.運用MATLAB R2016a來編寫算法的函數文件、腳本文件，并通過仿真優化獲取幾組較好的產品生產排序.

算法的有關系數設置：種群規模取400，進化代數取150，α取0.37，β取0.4.

3.2 結果輸出

運行算法程序，輸出獲得如圖4、5、6所示的每個目標函數的最佳解及其特性追蹤，如圖7所示的Pareto非支配解集.如表3所示為每個Pareto非劣解的3個目標函數值及其相應的生產排序.

圖4 迭代150次最大完工時間的最佳解及其特性追蹤Fig.4 The optimal solution and characteristic tracking of the makespan of 150 iterations圖5 迭代150次總拖期時間的最佳解及其特性追蹤Fig.5 The optimal solution and characteristic tracking of the total tardiness of 150 iterations

圖6 迭代150次總流程時間的最佳解及其特性追蹤Fig.6 The optimal solution and characteristic tracking of the total flow time of 150 iterations圖7 Pareto非支配解集Fig.7 Pareto nondominant solution set

表3 Pareto非支配解集Tab.3 Pareto nondominant solution set

3.3 結果分析

由圖4、5、6能夠得出，3個目標函數的均值靠近最佳解，算法趨向收斂.依據圖7、表3能夠得出：序號為2的解的總拖期時間和總流程時間對比其余12組解都大很多，但由于其最大完工時間最小，所以每次迭代都能探尋到該解；序號6和7的解的最大完工時間都較小，但其總流程時間都較大；剩下10組解的3個目標函數值都較好，且布局比較勻稱.運用Pareto非劣解集于流水車間調度中，生產者可以考慮實際加工條件下目標的主次之分，確定從優化所得的結果中遴選滿意的調度方案，達到符合實際的生產供給目的.比如，對于該企業的流水線，考慮當前最重要的是最小化產品的總拖期時間，所以對3個目標分別給予0.1、0.7和0.2的權重，將3個目標進行歸一化處理，獲取最好調度方案是w3,w2,w6,w1,w4,w5,w7.

4 結論

本文按照流水車間調度問題的理論與特征，創建以最小化最大完工時間、總拖期時間與總流程時間為優化目標的調度模型，同時結合某企業的流水線具體調度情況，使用帶自適應參數的改進NSGA-II算法求解該模型，獲取了比較中意的調度方案，表明NSGA-II算法在解決多目標流水車間調度問題上是可行的、有效的，并且為企業提供生產調度排序舉措參考.