改進(jìn)NSGA2算法求解柔性作業(yè)車間調(diào)度問題*

杜曉亮，張 楠，孟凡云，王金鶴

(青島理工大學(xué)信息與控制工程學(xué)院，青島 266000)

0 引言

車間調(diào)度是車間生產(chǎn)制造的一個(gè)重要環(huán)節(jié)，能夠充分利用現(xiàn)有的資源，合理的分配生產(chǎn)工序，減少加工時(shí)間和加工成本，優(yōu)化生產(chǎn)目標(biāo)，保證生產(chǎn)過程穩(wěn)定運(yùn)行。隨著先進(jìn)設(shè)備的出現(xiàn)，傳統(tǒng)的作業(yè)車間調(diào)度已經(jīng)不能滿足社會(huì)發(fā)展的需求，柔性車間調(diào)度問題則被大多數(shù)學(xué)者研究。由于在實(shí)際的生產(chǎn)活動(dòng)中需要考慮完工時(shí)間、總拖期時(shí)間、加工負(fù)載、最小成本等多個(gè)性能指標(biāo)，因此單目標(biāo)的柔性車間調(diào)度很難再反映實(shí)際的生產(chǎn)過程。

對(duì)于多目標(biāo)優(yōu)化問題，國(guó)內(nèi)外學(xué)者提出了多種求解該問題的算法。如DEB等[1]提出的NSGA2算法，ZITZLE等[2]提出的SPEA算法，KNOWLES等[3]提出的PESA算法等。目前，NSGA2算法使用較為廣泛。蔣浩等[4]在DEB提出的NSGA2算法的基礎(chǔ)上，提出了一種基于快速排序的非支配集構(gòu)造方法，并改進(jìn)了其種群構(gòu)造策略，設(shè)計(jì)了一類新的多目標(biāo)遺傳算法。

針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題，張超勇等[5]使用NSGA2算法并改進(jìn)其在非支配排序和精英選擇策略上的不足，設(shè)計(jì)了改進(jìn)的非支配排序遺傳算法，并用層次分析選出最優(yōu)妥協(xié)解。張守京等[6]針對(duì)NSGA2算法種群多樣性低，運(yùn)算速度慢等缺點(diǎn)，提出了基于擁擠度的自適應(yīng)交叉算子。陳輔斌等[7]引入免疫平衡原理改進(jìn)NSGA2算法的選擇策略和精英保留策略。陳明等[8]考慮了粒子最大、最小收斂速度及相應(yīng)邊界條件，設(shè)計(jì)了一種應(yīng)用于解決柔性生產(chǎn)調(diào)度的多目標(biāo)粒子群算法。

另外,PENG等[9]提出了基于遺傳算法的雙資源柔性作業(yè)車間調(diào)度問題，在考慮機(jī)器柔性的同時(shí)加入了工人柔性，使問題更加實(shí)際化。ZHANG等[10]提出了基于遺傳算法的可變鄰域搜索方法求解該問題。吳樹景等[11]提出了變鄰域保優(yōu)遺傳算法，將遺傳算法、變鄰域搜索算法與精英保留策略相結(jié)合，得到了運(yùn)算效率和求解性能均較好的混合算法。董海等[12]針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度中的工人柔性、機(jī)器柔性和并行工序柔性，結(jié)合入侵腫瘤生長(zhǎng)優(yōu)化算法的算法結(jié)構(gòu)和NSGA3中解的篩選機(jī)制，提出了一種多目標(biāo)優(yōu)化算法求解模型。

本文對(duì)傳統(tǒng)的NSGA2算法提出改進(jìn)，將工件的交貨期定為硬約束，針對(duì)最小化完工時(shí)間、最小總負(fù)載、最小成本三個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化，避免了種群多樣性降低造成的局部收斂同時(shí)加入鄰域搜索提高了算法的局部搜索能力。

1 多目標(biāo)柔性作業(yè)車間調(diào)度優(yōu)化模型

1.1 問題描述

柔性作業(yè)車間調(diào)度問題可以描述為有n個(gè)待加工工件在m臺(tái)機(jī)器上加工，工件集表示為J={J1,J2,…,Ji,…,Jn}，機(jī)器集為M={M1,M2,…Mk,…,Mm}。其中Ji表示第i個(gè)工件，Mk表示第k個(gè)加工機(jī)器。Ji工件有Oj道加工工序可以在不同的加工機(jī)器上進(jìn)行加工，每個(gè)工件內(nèi)的工序加工順序已定。Oij表示第i個(gè)工件的j道工序。選擇不同的加工機(jī)器會(huì)有不同的加工時(shí)間和能耗，因此調(diào)度的目標(biāo)就是將工序合理安排到各機(jī)器，使得完工時(shí)間、加工成本等目標(biāo)最小化。

同時(shí)，在加工過程中還應(yīng)滿足如下約束：一個(gè)工件內(nèi)前一道工序加工結(jié)束后才能開始下一道工序；一道工序一旦開始不能終止；一道工序同一時(shí)間只能被一個(gè)機(jī)器加工；一個(gè)機(jī)器同一時(shí)間只能加工一道工序；工件間優(yōu)先級(jí)是相同的；所有機(jī)器在0時(shí)刻都可用。

1.2 優(yōu)化目標(biāo)函數(shù)

在實(shí)際的生產(chǎn)車間中，能夠及時(shí)完成車間任務(wù)、降低車間的生產(chǎn)成本并且使機(jī)器負(fù)載最小才能保證企業(yè)的經(jīng)濟(jì)效益。本文綜合了完工時(shí)間、加工成本、機(jī)器總負(fù)載多個(gè)目標(biāo)建立如下模型：

(1)

(2)

(3)

式(1)～式(3)中，目標(biāo)函數(shù)f1～f3分別為最小化最大完工時(shí)間、最小化機(jī)器總負(fù)載、最小化加工成本；Cj為Jj的完工時(shí)間；pijk為Oij在機(jī)器k上的加工時(shí)間；xijk為決策變量；Oij在第k個(gè)加工機(jī)器上加工時(shí)，xijk=1，否則為0；CMk為第k個(gè)機(jī)器的單位時(shí)間加工費(fèi)用。

2 基于改進(jìn)NSGA2的多目標(biāo)柔性作業(yè)車間調(diào)度算法

2.1 求解過程

基于改進(jìn)NSGA2算法的多目標(biāo)柔性作業(yè)車間調(diào)度算法流程圖如圖1所示。

圖1 多目標(biāo)柔性作業(yè)車間調(diào)度問題求解流程圖

首先初始化種群，設(shè)置種群數(shù)量為200，然后進(jìn)行非支配排序和擁擠度計(jì)算，把種群中的個(gè)體按照非支配排序的等級(jí)進(jìn)行分級(jí)并計(jì)算出個(gè)體的擁擠度，之后進(jìn)行選擇交叉變異產(chǎn)生新種群，將父代種群和子代種群合并后再進(jìn)行非支配排序和擁擠度計(jì)算，采用改進(jìn)的精英保留策略生成新的種群，再進(jìn)行鄰域搜索，提高算法的局部搜索能力，最后非支配快速排序完成后進(jìn)行下一次迭代，直到滿足終止條件。

達(dá)到終止條件后，所得結(jié)果為一個(gè)包含多個(gè)解的Pareto最優(yōu)解集。根據(jù)不同目標(biāo)函數(shù)的權(quán)重進(jìn)行歸一化后選出最滿意的解。對(duì)最滿意解進(jìn)行解碼輸出調(diào)度甘特圖。

2.2 算法設(shè)計(jì)

2.2.1 解碼和編碼

本文采用的是基于實(shí)數(shù)的雙層編碼方式。編碼結(jié)果如圖2所示。第一層編碼是對(duì)工序進(jìn)行編碼。基因?yàn)閇0,1]之間的實(shí)數(shù)，經(jīng)過排序后得到排序編碼并對(duì)工序順序編碼重排后得到工序編碼。如：有兩個(gè)工件，第一個(gè)工件有兩道工序，第二個(gè)工件有三道工序。

圖2 基于實(shí)數(shù)的雙層編碼

工序順序編碼為S0=[1,1,2,2,2]。

第一層編碼首先產(chǎn)生[0,1]之間的實(shí)數(shù)為：

0.540.120.680.330

那么排序后的排序編碼為：S=[4,2,5,3,1]，用S對(duì)S0進(jìn)行重排后得到工序編碼為：S2=[2,1,2,2,1]。

第二層編碼是為工序選用加工機(jī)器編碼?；蛳蛳氯≌蟊硎驹摴ば虿捎闷涞趲讉€(gè)可用加工機(jī)器。如：

2.381.573.232.461.68

向下取整后為：

21321

第一位的2表示第一個(gè)零件第一個(gè)工序用它的第二個(gè)可用機(jī)器加工；第二位的1表示第一個(gè)零件的第二個(gè)工序用它的第一個(gè)可用機(jī)器加工，以此類推。

解碼采用貪婪式解碼算法。具體如下：首先按照工序在序列上的順序進(jìn)行解碼，然后將每道工序安排到該工序的加工機(jī)器上的盡可能早的時(shí)刻進(jìn)行加工，直到所有的工序都安排在最佳可行的地方為止。

2.2.2 Pareto排序

本文采用文獻(xiàn)[1]提出的快速非支配排序算法，時(shí)間復(fù)雜度為O(MN2)。

2.2.3 選擇交叉變異

本文采用二元聯(lián)賽選擇算法，優(yōu)先選擇快速非支配排序過程中等級(jí)低的個(gè)體，當(dāng)?shù)燃?jí)相同時(shí)，選擇擁擠度小的個(gè)體。交叉方式為兩點(diǎn)交叉，變異方式為單點(diǎn)變異。

2.2.4 改進(jìn)的精英保留

原始的NSGA2算法中，根據(jù)支配關(guān)系，將支配等級(jí)低的個(gè)體加入到新種群中，等級(jí)相同時(shí)將擁擠度小的個(gè)體放入種群中，直到種群規(guī)模達(dá)到N。這種精英保留策略是將所有的精英進(jìn)行保留，可能會(huì)導(dǎo)致快速收斂或者收斂于局部最優(yōu)解。因此，本文設(shè)計(jì)了改進(jìn)的精英保留策略如圖3所示。設(shè)置參數(shù)α，將前N×α個(gè)個(gè)體直接加入到新種群中，剩余的N×(1-α)個(gè)個(gè)體從次優(yōu)平面上隨機(jī)選擇。

圖3 改進(jìn)的精英保留策略

2.2.5 鄰域搜索

根據(jù)編碼結(jié)構(gòu)的特點(diǎn)，對(duì)種群中的個(gè)體進(jìn)行鄰域搜索。鄰域搜索方式為單點(diǎn)變異，如圖4所示，若選擇變異基因位于工序部分，則對(duì)變異后所有工序編碼部分基因按2.2.1節(jié)描述的方式重排后進(jìn)行解碼計(jì)算目標(biāo)函數(shù)值；若變異基因位于機(jī)器編碼部分，則從該工序可選機(jī)器中隨機(jī)選取其他機(jī)器代替，而后計(jì)算目標(biāo)函數(shù)值。將鄰域搜索前后的值進(jìn)行比較，將最優(yōu)值進(jìn)行保留。

圖4 基于單點(diǎn)變異的鄰域搜索

3 仿真與結(jié)果分析

3.1 標(biāo)準(zhǔn)實(shí)例實(shí)驗(yàn)測(cè)試

為了驗(yàn)證本文算法的有效性，采用文獻(xiàn)[13]不帶釋放時(shí)間的8×8標(biāo)準(zhǔn)實(shí)例進(jìn)行測(cè)試。測(cè)試結(jié)果如表1所示，表中給出了GA、SPT[14]、張算法[5]的結(jié)果和本文算法的結(jié)果。由于Pareto解有多個(gè)，選取其中一個(gè)進(jìn)行對(duì)比。從表中可以看出，本文算法在最大完工時(shí)間和機(jī)器最大負(fù)載兩個(gè)性能指標(biāo)上優(yōu)于或等于其他算法；在總負(fù)載時(shí)間上僅次于張算法。由此可見，本文算法在求解多目標(biāo)柔性作業(yè)車間調(diào)度上能得到比較好的結(jié)果。

表1 8×8實(shí)例測(cè)試結(jié)果的比較

3.2 實(shí)例仿真

為進(jìn)一步體現(xiàn)算法的實(shí)用性，采用文獻(xiàn)[6]中的數(shù)據(jù)如表2所示，并合理加入機(jī)器生產(chǎn)成本數(shù)據(jù)進(jìn)行仿真。優(yōu)化目標(biāo)為最大完工時(shí)間、最大負(fù)載、最大加工成本。參數(shù)設(shè)置如下：種群規(guī)模設(shè)置為200，迭代次數(shù)為80，交叉概率為0.8，變異概率為0.1，鄰域搜索次數(shù)為4，精英保留系數(shù)為0.9，目標(biāo)函數(shù)的權(quán)重分別為0.6、0.2、0.2。通過MATLAB對(duì)以上實(shí)例進(jìn)行仿真分析，得到各個(gè)調(diào)度目標(biāo)進(jìn)化過程曲線圖、Pareto解集圖、最優(yōu)調(diào)度甘特圖。

表2 6×6柔性作業(yè)車間調(diào)度問題實(shí)例數(shù)據(jù)

圖5中隨著迭代次數(shù)增加，各個(gè)目標(biāo)函數(shù)值不斷進(jìn)行優(yōu)化，算法具有良好的收斂性。在迭代次數(shù)達(dá)到50次之后，目標(biāo)函數(shù)值趨于平穩(wěn)。為了體現(xiàn)改進(jìn)的NSGA2算法的有效性，繪制了如圖6所示的帕累托前沿對(duì)比圖。圖中可以較明顯的看出經(jīng)改進(jìn)的NSGA2算法可以得到更好的一組解。

(c) 機(jī)器總負(fù)載的迭代曲線圖5 種群進(jìn)化迭代圖

(a) 完工時(shí)間的迭代曲線 (b) 生產(chǎn)成本的迭代曲線

圖6 帕累托前沿圖 圖7 改進(jìn)后最優(yōu)調(diào)度甘特圖

本文算法在迭代完成后，會(huì)得到一組Pareto解集，去掉重復(fù)解后得到如表3所示的最優(yōu)解集表。表中每個(gè)解均為最優(yōu)解，且各個(gè)解之間互不支配。為了考慮問題的實(shí)際性，為每個(gè)目標(biāo)函數(shù)設(shè)置不同權(quán)重，完工時(shí)間、機(jī)器總負(fù)載、生產(chǎn)成本分別為0.6，0.2，0.2。對(duì)各個(gè)目標(biāo)函數(shù)進(jìn)行歸一化處理后，得到最優(yōu)調(diào)度甘特圖。圖7為改進(jìn)后算法得到的最優(yōu)調(diào)度甘特圖。圖中6-1表示第6個(gè)工件的第1道工序；3-2表示第3個(gè)工件的第2道工序。算法改進(jìn)前后各個(gè)目標(biāo)函數(shù)值對(duì)比如表4所示，原始NSGA2算法中最大完工時(shí)間為69，機(jī)器總負(fù)載為260，生產(chǎn)成本為1 011.5。改進(jìn)后算法最大完工時(shí)間為61，機(jī)器總負(fù)載為260，生產(chǎn)成本為995。經(jīng)對(duì)比發(fā)現(xiàn)，完工時(shí)間優(yōu)化了8個(gè)單位，優(yōu)化了11.6%；機(jī)器總負(fù)載相同；生產(chǎn)成本優(yōu)化了16.5個(gè)單位，優(yōu)化了1.6%。

表3 Pareto最優(yōu)解集

表4 算法改進(jìn)前后各個(gè)目標(biāo)函數(shù)值對(duì)比分析

4 結(jié)束語

針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題，本文設(shè)計(jì)了改進(jìn)的NSGA2算法。算法設(shè)計(jì)了一種基于實(shí)數(shù)的雙層編碼方式，避免了種群中的個(gè)體在交叉變異過程中產(chǎn)生不可行解。針對(duì)原始NSGA2算法在種群迭代過程中出現(xiàn)的提前收斂或局部收斂問題，設(shè)計(jì)了改進(jìn)的精英保留算法，另外增加了鄰域搜索提高了算法的局部搜索能力。通過仿真實(shí)驗(yàn)分析，驗(yàn)證了算法的有效性和可行性。此外還可以考慮將本文算法應(yīng)用于實(shí)際車間生產(chǎn)過程中，以滿足實(shí)際生產(chǎn)的需求。