混合NSGA-Ⅱ算法求解多目標柔性作業車間調度問題*

景志強，王兆輝，高 琦

(山東大學 機械工程學院 CAD/CAM研究所，濟南 250061)

0 引言

生產調度是影響制造業的重要因素，調度方法的研究與實施，對于企業提高生產效率、降低生產成本、節約能耗以及提高顧客滿意度方面都起到了十分重要的作用。柔性作業車間調度(Flexible job scheduling problem，FJSP)是對傳統作業車間調度問題的擴展，其中工件的某工序允許在多臺機器中的某幾臺機器上加工，更加貼近實際。因而，柔性制造系統在當前的機械加工行業使用十分廣泛。FJSP不僅需要確定工序加工的順序，還要為每個工序分配機器，是一個復雜的NP-hard問題。

針對多目標優化問題，很多學者進行了研究。牛琳、劉燚[1-2]采用模擬退火算法融合遺傳算法對調度領域進行了研究，獲取優化調度策略。金敏[3]則是將遺傳算法與粒子群算法相結合，提出了一種遺傳算法和粒子群優化的多子群分層混合算法。張靜[4]提出Baldwinian學習和模擬退火技術相結合的多目標局部搜索策略。張超勇[5]設計了一種改進的非支配排序遺傳算法，改善原本算法在精英選擇策略上的不足。鞠海華等[6-8]都是基于NSGA-II算法來對多目標調度問題進行求解。

從上述研究可以看出，單一算法由于搜索機制和進化方式，都會有各自的不足，因而采用混合算法求解將會改善尋優過程。目前的研究多為使用NSGA-II算法來求解，雖然其在多目標優化問題上體現了良好的求解能力，但在保持種群的多樣性方面仍存在不足，為改善求解結果，引入模擬退火算法來執行選擇過程，為子代提供更多的隨機個體，增強整個算法的全局搜索能力。

1 FJSP調度模型

1.1 問題描述

柔性作業車間調度問題可描述為N個不同的工件在M臺不同的機器上加工，每個工件有P道工序，且工序間的有先后約束。工件的每道工序可由M臺機器上的一臺或多臺機器上加工，工件在各機器上的加工時間已知。確定N個工件在每臺機器上的最優加工順序，使得優化目標達到最優。

調度過程中要滿足以下的約束條件：所有機器剛開始時均處空閑狀態，在零時刻所有的工件都可進入生產系統進行加工；不同工件的工序之間沒有先后約束，工件之間具備相同的優先級；工序的加工時間是確定的，某道工序完成后才能開始后道工序；工序一旦進行不能中斷，同一時刻一臺機器只能加工一道工序。

1.2 多目標優化模型

在車間調度的研究中常以最大完工時間、最大機器負荷、機器總負荷、加工質量、加工工期、加工成本、設備利用率、總拖期時間這些指標的組合作為多目標進行研究。

本文以最大完工時間、提前/拖期懲罰函數、生產總成本作為FJSP的多目標優化函數，對應的優化模型為：

(1)最大完工時間

調度的目標為確定每個工件的加工機器以及在加工開始和結束的時間，優化的方向為使得最大完工時間最小。其中ti表示工件i的完工時間，公式如下：

T=min(max(ti))

(1)

(2)提前/拖期懲罰函數

工件的加工應該滿足交貨期要求，而且也不應過早完成，造成庫存浪費。最理想的結果是在各自的交貨期時刻完成，因而要考慮提前/拖期懲罰函數，優化的方向為使得懲罰函數值最小。其中N為工件數量，M為機器數量，ri提前懲罰系數和wi拖期懲罰系數，di為工件的交貨期，公式如下：

(2)

(3)成本函數

成本方面，本文只考慮機器加工過程中的成本。其中Xijk為工件i的工序j在機器k上的加工時間，Cijk為工件i的工序j在機器k上的單位成本。

(3)

2 混合NSGA-Ⅱ算法設計

2.1 基因編碼

針對柔性作業車間調度的復雜性，本文采用雙層編碼原則。個體基因序列的前半部分代表工序的順序，后半部分代表對應的加工機器。如3工件、每個工件3工序、6機器的調度問題的一個調度 [3 1 2 1 1 3 2 2 3 1 2 1 5 3 4 6 5 4]。

所代表的加工順序為：工件3的第一道工序(加工機器為1)→工件1的第一道工序(加工機器為2)→工件2的第一道工序(加工機器為1)→工件1的第二道工序(加工機器為5)依次類推。

2.2 選擇算子

本文采用模擬退火算法與模擬二進制選擇相結合的方法對已進行非支配排序的個體進行選擇。在原有模擬二進制的基礎上，對于序值和擁擠距離這兩個選擇參數進行模擬退火操作，以實現全局搜索。操作步驟如下：

若RiRj，個體i的序值劣于個體j，按照Metropolis準則來進行操作，而且這個概率隨著時間推移逐漸降低。倘若Ri=Rj則同理對擁擠距離進行模擬退火操作。模擬退火對應的概率公式為：

(4)

2.3 交叉與變異

交叉采用單點交叉的方式，變異采用線性的自適應變異來實現種群的進化，隨著種群進化代數的不斷增加，其變異概率會不斷增大，加強算法的全局搜索能力。

2.4 算法流程

混合NSGA-Ⅱ算法是以遺傳算法為基礎(GA)，通過引入非支配排序、個體擁擠距離、精英保留與模擬退火的多目標優化算法。通過對種群中的個體進行非支配排序得到個體序值與擁擠距離，使用模擬退火與模擬二進制相結合的選擇原則，進行選擇操作。算法流程如圖1所示。

圖1 混合NSGA-Ⅱ算法流程圖

2.5 算法驗證

本文將混合NSGA-Ⅱ算法與NSGA-Ⅱ算法進行了對比分析，針對的基準問題為一個雙目標和一個三目標函數的優化，實驗結果如下圖，圖中圓圈代表混合NSGA-Ⅱ算法的Pareto前端，星號代表NSGA-Ⅱ算法的Pareto前端。使用Matlab軟件編程，得到結果如圖2、圖3所示，雙目標優化結果對比見表1。

圖2 混合NSGA-Ⅱ算法與NSGA-Ⅱ算法雙目標求解結果對比圖

圖3 混合NSGA-Ⅱ算法與NSGA-Ⅱ算法三目標求解結果對比圖

雙目標f(x1)f(x2)優化前(0.28,1)(0,1.7)優化后(0.28,1)(0,7.8)

可以明顯看出混合NSGA-Ⅱ算法的Pareto前端的范圍更廣，說明其全局搜索能力更強。

3 車間調度仿真實例

本文參考文獻6中的相關數據，對以最大完工時間、提前/拖期懲罰函數、生產總成本為優化目標車間調度問題進行驗證。文獻中的數據是針對6工件，每個工件有6個工序，10臺機器的FJSP問題的研究。

本文新增了懲罰函數以及成本的相關參數，工序的可選機器號如表1所示，工序的加工時間如表3所示，工件懲罰函數相關參數如表4所示，各機床的單位時間成本如表5所示。

表2 各工序的可用機器

表3 各工序加工時間

表4 各工件懲罰函數相關參數

表5 各機床的單位時間成本

得到如圖4所示的Pareto前端，以及以如圖5所示Pareto前端第一個解的甘特圖。甘特圖中的三位標號，第一位代表零件編號，后兩位為零件工序號。如503，表示工件5的第3道工序。

針對完工時間、提前/拖期懲罰以及成本的三目標優化問題，求解得到了完整的Pareto前端，由圖4可以明顯看出，三個目標之間相互影響。在實際應用過程中，企業可根據實際情況選取合適的解，如注重減少成本則選取成本值較小的解。隨后可以得到相應的甘特圖，用于指導實際生產。

圖4 混合NSGA-Ⅱ算法求解FJSP的Pareto前端

圖5 柔性車間調度甘特圖

4 總結

本文針對柔性作業車間調度問題，摒棄了將多目標轉換為單目標的方式，使用改進的NSGA-Ⅱ算法，對多目標問題進行直接求解，并在求解過程中保持了解的多樣性，得到車間調度的解決方案，為生產車間提供一系列可參考的調度，實現了最優調度方案的獲取。

該研究為相關問題的解決提供新思路，可以進一步向流水車間調度問題或其他調度問題進行拓展。