混合NSGA-Ⅱ算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題*

景志強(qiáng)，王兆輝，高 琦

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

0 引言

生產(chǎn)調(diào)度是影響制造業(yè)的重要因素，調(diào)度方法的研究與實(shí)施，對(duì)于企業(yè)提高生產(chǎn)效率、降低生產(chǎn)成本、節(jié)約能耗以及提高顧客滿意度方面都起到了十分重要的作用。柔性作業(yè)車間調(diào)度(Flexible job scheduling problem，F(xiàn)JSP)是對(duì)傳統(tǒng)作業(yè)車間調(diào)度問題的擴(kuò)展，其中工件的某工序允許在多臺(tái)機(jī)器中的某幾臺(tái)機(jī)器上加工，更加貼近實(shí)際。因而，柔性制造系統(tǒng)在當(dāng)前的機(jī)械加工行業(yè)使用十分廣泛。FJSP不僅需要確定工序加工的順序，還要為每個(gè)工序分配機(jī)器，是一個(gè)復(fù)雜的NP-hard問題。

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

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

1 FJSP調(diào)度模型

1.1 問題描述

柔性作業(yè)車間調(diào)度問題可描述為N個(gè)不同的工件在M臺(tái)不同的機(jī)器上加工，每個(gè)工件有P道工序，且工序間的有先后約束。工件的每道工序可由M臺(tái)機(jī)器上的一臺(tái)或多臺(tái)機(jī)器上加工，工件在各機(jī)器上的加工時(shí)間已知。確定N個(gè)工件在每臺(tái)機(jī)器上的最優(yōu)加工順序，使得優(yōu)化目標(biāo)達(dá)到最優(yōu)。

調(diào)度過程中要滿足以下的約束條件：所有機(jī)器剛開始時(shí)均處空閑狀態(tài)，在零時(shí)刻所有的工件都可進(jìn)入生產(chǎn)系統(tǒng)進(jìn)行加工；不同工件的工序之間沒有先后約束，工件之間具備相同的優(yōu)先級(jí)；工序的加工時(shí)間是確定的，某道工序完成后才能開始后道工序；工序一旦進(jìn)行不能中斷，同一時(shí)刻一臺(tái)機(jī)器只能加工一道工序。

1.2 多目標(biāo)優(yōu)化模型

在車間調(diào)度的研究中常以最大完工時(shí)間、最大機(jī)器負(fù)荷、機(jī)器總負(fù)荷、加工質(zhì)量、加工工期、加工成本、設(shè)備利用率、總拖期時(shí)間這些指標(biāo)的組合作為多目標(biāo)進(jìn)行研究。

本文以最大完工時(shí)間、提前/拖期懲罰函數(shù)、生產(chǎn)總成本作為FJSP的多目標(biāo)優(yōu)化函數(shù)，對(duì)應(yīng)的優(yōu)化模型為：

(1)最大完工時(shí)間

調(diào)度的目標(biāo)為確定每個(gè)工件的加工機(jī)器以及在加工開始和結(jié)束的時(shí)間，優(yōu)化的方向?yàn)槭沟米畲笸旯r(shí)間最小。其中ti表示工件i的完工時(shí)間，公式如下：

T=min(max(ti))

(1)

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

工件的加工應(yīng)該滿足交貨期要求，而且也不應(yīng)過早完成，造成庫存浪費(fèi)。最理想的結(jié)果是在各自的交貨期時(shí)刻完成，因而要考慮提前/拖期懲罰函數(shù)，優(yōu)化的方向?yàn)槭沟脩土P函數(shù)值最小。其中N為工件數(shù)量，M為機(jī)器數(shù)量，ri提前懲罰系數(shù)和wi拖期懲罰系數(shù)，di為工件的交貨期，公式如下：

(2)

(3)成本函數(shù)

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

(3)

2 混合NSGA-Ⅱ算法設(shè)計(jì)

2.1 基因編碼

針對(duì)柔性作業(yè)車間調(diào)度的復(fù)雜性，本文采用雙層編碼原則。個(gè)體基因序列的前半部分代表工序的順序，后半部分代表對(duì)應(yīng)的加工機(jī)器。如3工件、每個(gè)工件3工序、6機(jī)器的調(diào)度問題的一個(gè)調(diào)度 [3 1 2 1 1 3 2 2 3 1 2 1 5 3 4 6 5 4]。

所代表的加工順序?yàn)椋汗ぜ?的第一道工序(加工機(jī)器為1)→工件1的第一道工序(加工機(jī)器為2)→工件2的第一道工序(加工機(jī)器為1)→工件1的第二道工序(加工機(jī)器為5)依次類推。

2.2 選擇算子

本文采用模擬退火算法與模擬二進(jìn)制選擇相結(jié)合的方法對(duì)已進(jìn)行非支配排序的個(gè)體進(jìn)行選擇。在原有模擬二進(jìn)制的基礎(chǔ)上，對(duì)于序值和擁擠距離這兩個(gè)選擇參數(shù)進(jìn)行模擬退火操作，以實(shí)現(xiàn)全局搜索。操作步驟如下：

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

(4)

2.3 交叉與變異

交叉采用單點(diǎn)交叉的方式，變異采用線性的自適應(yīng)變異來實(shí)現(xiàn)種群的進(jìn)化，隨著種群進(jìn)化代數(shù)的不斷增加，其變異概率會(huì)不斷增大，加強(qiáng)算法的全局搜索能力。

2.4 算法流程

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

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

2.5 算法驗(yàn)證

本文將混合NSGA-Ⅱ算法與NSGA-Ⅱ算法進(jìn)行了對(duì)比分析，針對(duì)的基準(zhǔn)問題為一個(gè)雙目標(biāo)和一個(gè)三目標(biāo)函數(shù)的優(yōu)化，實(shí)驗(yàn)結(jié)果如下圖，圖中圓圈代表混合NSGA-Ⅱ算法的Pareto前端，星號(hào)代表NSGA-Ⅱ算法的Pareto前端。使用Matlab軟件編程，得到結(jié)果如圖2、圖3所示，雙目標(biāo)優(yōu)化結(jié)果對(duì)比見表1。

圖2 混合NSGA-Ⅱ算法與NSGA-Ⅱ算法雙目標(biāo)求解結(jié)果對(duì)比圖

圖3 混合NSGA-Ⅱ算法與NSGA-Ⅱ算法三目標(biāo)求解結(jié)果對(duì)比圖

雙目標(biāo)f(x1)f(x2)優(yōu)化前(0.28,1)(0,1.7)優(yōu)化后(0.28,1)(0,7.8)

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

3 車間調(diào)度仿真實(shí)例

本文參考文獻(xiàn)6中的相關(guān)數(shù)據(jù)，對(duì)以最大完工時(shí)間、提前/拖期懲罰函數(shù)、生產(chǎn)總成本為優(yōu)化目標(biāo)車間調(diào)度問題進(jìn)行驗(yàn)證。文獻(xiàn)中的數(shù)據(jù)是針對(duì)6工件，每個(gè)工件有6個(gè)工序，10臺(tái)機(jī)器的FJSP問題的研究。

本文新增了懲罰函數(shù)以及成本的相關(guān)參數(shù)，工序的可選機(jī)器號(hào)如表1所示，工序的加工時(shí)間如表3所示，工件懲罰函數(shù)相關(guān)參數(shù)如表4所示，各機(jī)床的單位時(shí)間成本如表5所示。

表2 各工序的可用機(jī)器

表3 各工序加工時(shí)間

表4 各工件懲罰函數(shù)相關(guān)參數(shù)

表5 各機(jī)床的單位時(shí)間成本

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

針對(duì)完工時(shí)間、提前/拖期懲罰以及成本的三目標(biāo)優(yōu)化問題，求解得到了完整的Pareto前端，由圖4可以明顯看出，三個(gè)目標(biāo)之間相互影響。在實(shí)際應(yīng)用過程中，企業(yè)可根據(jù)實(shí)際情況選取合適的解，如注重減少成本則選取成本值較小的解。隨后可以得到相應(yīng)的甘特圖，用于指導(dǎo)實(shí)際生產(chǎn)。

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

圖5 柔性車間調(diào)度甘特圖

4 總結(jié)

本文針對(duì)柔性作業(yè)車間調(diào)度問題，摒棄了將多目標(biāo)轉(zhuǎn)換為單目標(biāo)的方式，使用改進(jìn)的NSGA-Ⅱ算法，對(duì)多目標(biāo)問題進(jìn)行直接求解，并在求解過程中保持了解的多樣性，得到車間調(diào)度的解決方案，為生產(chǎn)車間提供一系列可參考的調(diào)度，實(shí)現(xiàn)了最優(yōu)調(diào)度方案的獲取。

該研究為相關(guān)問題的解決提供新思路，可以進(jìn)一步向流水車間調(diào)度問題或其他調(diào)度問題進(jìn)行拓展。