多種群NSGA-Ⅱ改進(jìn)算法的大規(guī)模柔性作業(yè)車間調(diào)度問(wèn)題*

陳自豪，陳松航，陳 豪

(1.福建省復(fù)雜動(dòng)態(tài)系統(tǒng)智能辨識(shí)與控制實(shí)驗(yàn)室 泉州裝備制造研究所，福建 泉州 362200；2.中北大學(xué) 電氣與控制工程學(xué)院，山西 太原 030051)

0 引 言

柔性作業(yè)車間調(diào)度問(wèn)題(flexible job-shop scheduling problem,FJSP)可以被描述為每個(gè)工件的每道工序只能在一臺(tái)機(jī)器上加工，并且只能加工一次，每道工序可以對(duì)機(jī)器進(jìn)行選擇，且加工時(shí)間確定。FJSP本質(zhì)上是一種對(duì)資源進(jìn)行優(yōu)化配置的策略，是一類NP-hard問(wèn)題。

遺傳算法(genetic algorithm,GA)由于其簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理問(wèn)題等特點(diǎn)被廣泛應(yīng)用于求解FJSP。張國(guó)輝等人[1]改進(jìn)了種群初始化的方法，應(yīng)用全局搜索、局部搜索與隨機(jī)搜索相結(jié)合的策略，提升了算法的收斂速度。Pezzella F[2]在遺傳算法框架中整合多種選擇和和交叉策略，改進(jìn)種群初始化方法驗(yàn)證了遺傳算法求解FJSP的有效性。陳輔斌等人[3]通過(guò)引入免疫平衡原理改進(jìn)了NSGA-Ⅱ算法的選擇策略與精英保留策略解決了算法收斂性能不足的缺陷。Wan M[4]在遺傳算法中整合多種選擇策略并使用并行機(jī)制處理基因序列對(duì)個(gè)體進(jìn)行編碼改善了算法性能。FJSP中傳統(tǒng)基準(zhǔn)實(shí)例規(guī)模一般都不超過(guò)20×50，基準(zhǔn)實(shí)例已不能滿足對(duì)實(shí)際生產(chǎn)過(guò)程的算法模擬。

本文針對(duì)FJSP基準(zhǔn)實(shí)例的特點(diǎn)與規(guī)則編寫腳本生成大規(guī)模測(cè)試集來(lái)模擬大規(guī)模FJSP問(wèn)題，提出了一種多種群NSGA-Ⅱ改進(jìn)算法來(lái)求解，并通過(guò)大規(guī)?；鶞?zhǔn)實(shí)例驗(yàn)證了該算法的可行性和有效性。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

本文研究的是FJSP中代表性的偏柔性作業(yè)車間調(diào)度問(wèn)題(partial flexible job-shop scheduling problem，PFJSP)，部分工序可以選擇工廠中的任意一臺(tái)機(jī)器進(jìn)行加工，剩余部分的工序就只能選擇在一些特定機(jī)器上進(jìn)行加工[5]。

1.2 大規(guī)模數(shù)據(jù)集描述

FJSP問(wèn)題的一個(gè)傳統(tǒng)基準(zhǔn)實(shí)例的片段如下

……

每組數(shù)據(jù)的第一行首數(shù)字代表工件數(shù)，第二個(gè)數(shù)字代表機(jī)器數(shù)，第三個(gè)數(shù)字表示每一道工序平均可供選擇加工的機(jī)器數(shù)。第一行即表示：2個(gè)工件，3臺(tái)機(jī)器，每道工序平均有1臺(tái)機(jī)器可以選擇。

第二行開始每行表示一個(gè)工件。第二行即表示：第一個(gè)數(shù)字2代表加工第一個(gè)工件有兩道工序，第二個(gè)2代表加工工序1有兩臺(tái)機(jī)器可供選擇，接下來(lái)(1 2)，(3 4)分別表示工序1在機(jī)器1上加工用時(shí)為2，在第3臺(tái)機(jī)器上加工用時(shí)為4，以此類推[6]，直至結(jié)束。

根據(jù)上述數(shù)據(jù)特點(diǎn)，采用Python語(yǔ)法和關(guān)鍵詞對(duì)大規(guī)模數(shù)據(jù)生成腳本進(jìn)行描述如下。

設(shè)置初始變量：m個(gè)工件，n臺(tái)機(jī)器，numOjob每個(gè)工件的工序數(shù) for i in range(m):

for j in range(NumOfJob):

for k in range(random.randint(1,n)):

數(shù)據(jù)對(duì)=(機(jī)器號(hào)，對(duì)應(yīng)加工用時(shí))

return數(shù)據(jù)對(duì)=random.randint(1,n)+數(shù)據(jù)對(duì)

return每個(gè)工件的加工數(shù)據(jù)=工序數(shù)+數(shù)據(jù)對(duì)

return所有工件的加工數(shù)據(jù)(沒(méi)有第一行)

1.3 模型構(gòu)建

在求解FJSP的過(guò)程中，需要一些常用的指標(biāo)。根據(jù)工廠的實(shí)際需求，使用了3個(gè)貼近生產(chǎn)成本的指標(biāo)來(lái)構(gòu)建模型。

最大完工時(shí)間最?。好總€(gè)工件從開始加工時(shí)刻到最后一道工序完成時(shí)刻的耗時(shí)便是完工時(shí)間 ，所有工件中加工耗時(shí)中最大的那個(gè)時(shí)間就是最大完工時(shí)間[7]。最大完工時(shí)間體現(xiàn)車間生產(chǎn)效率，是FJSP最根本的評(píng)價(jià)指標(biāo)，也是FJSP研究中應(yīng)用最廣泛的評(píng)價(jià)指標(biāo)之一。即

(1)

機(jī)器最大負(fù)荷最?。涸谇蠼釬JSP時(shí)，因機(jī)器選擇問(wèn)題會(huì)造成機(jī)器負(fù)荷不平衡，從而無(wú)法提高機(jī)器利用率而產(chǎn)生效率瓶頸。為克服由于調(diào)度方案不同而引發(fā)的機(jī)器負(fù)荷不平衡問(wèn)題，也為提高每臺(tái)機(jī)器的利用率，采用機(jī)器最大負(fù)荷為評(píng)價(jià)指標(biāo)，如下

(2)

總機(jī)器負(fù)荷最小：在求解FJSP時(shí)，不同機(jī)器加工同一道工序耗時(shí)有差異，這會(huì)使總的機(jī)器負(fù)荷會(huì)隨著調(diào)度方案的變化而波動(dòng)。依據(jù)工廠實(shí)際需求，保證其他指標(biāo)不降低的情況下，減少所有機(jī)器的總消耗降低成本。即

(3)

根據(jù)實(shí)際車間生產(chǎn)中目標(biāo)值f1、f2、f3對(duì)生產(chǎn)效率產(chǎn)生影響的大小，設(shè)定三個(gè)目標(biāo)值f1、f2、f3的權(quán)重值ω1，ω2，ω3分別為0.5，0.3，0.2來(lái)構(gòu)造評(píng)價(jià)函數(shù)F如式(4)所示，使用評(píng)價(jià)函數(shù)F來(lái)評(píng)價(jià)算法在求解FJSP問(wèn)題中所得到最優(yōu)解的優(yōu)劣

F=ω1f1+ω2f2+ω3f3

(4)

2 多種群NSGA-Ⅱ改進(jìn)算法

2.1 基于工序和機(jī)器的分段編碼策略

求解FJSP這類離散問(wèn)題時(shí)，優(yōu)秀的編碼是算法求得最優(yōu)解的前提與保證。FJSP編碼即要有加工工序的先后順序編碼，也要包含每道工序可供選擇加工機(jī)器編碼，因此選擇融合工序和機(jī)器的分段編碼方式[8]。

基于工序和機(jī)器的分段編碼由工序編碼段與機(jī)器編碼段兩部分組成：工序編碼段決定每道工序的加工順序，機(jī)器編碼段決定工件的某道工序由哪臺(tái)機(jī)器來(lái)加工。如圖1所示染色體編碼表示有3個(gè)工件共8道工序。

圖1 染色體編碼

2.2 隨機(jī)式選擇與啟發(fā)式選擇初始化

針對(duì)FJSP的特點(diǎn)，采用隨機(jī)式選擇與啟發(fā)式選擇相結(jié)合的方法，既加快了運(yùn)行時(shí)間又避免了算法因?yàn)檫^(guò)早的收斂從而陷入局部最優(yōu)。隨機(jī)式選擇：加工工序的機(jī)器在可選機(jī)器集中隨機(jī)選擇一臺(tái)。啟發(fā)式選擇：工序的加工機(jī)器在可選機(jī)器集中選擇加工時(shí)間最短的那臺(tái)機(jī)器。

通過(guò)實(shí)驗(yàn)對(duì)比，在隨機(jī)式選擇、啟發(fā)式選擇的多種比例中選擇了效果較好的1∶1比例，即種群中50 %的個(gè)體隨機(jī)式選擇，50 %的個(gè)體啟發(fā)式選擇。

2.3 基于工序與機(jī)器的分段交叉與對(duì)應(yīng)變異

工序部分的交叉：基于工件優(yōu)先順序的交叉(precedence preserving order-based crossover，POX)得到的子代總是可行的，可以比其他的交叉方式獲得更好的結(jié)果[9]。POX交叉如圖2，具體執(zhí)行步驟如下：1)將工件集J={J1,J2,…,Jn}隨機(jī)分成兩個(gè)非空子集Jobset1和Jobset2，如Jobset1={2,3}和Jobset2={1,4};2)將父代1屬于Jobset1的所有基因位置對(duì)應(yīng)的復(fù)制到子代1中，將父代2中屬于Jobset2的基因去掉，然后將剩余的基因依次放入子代中。

圖2 POX交叉

A 種群機(jī)器部分交叉：為了保持機(jī)器部分的基因順序不變，采用均勻交叉如圖3。具體步驟如下：1)工序長(zhǎng)度I的區(qū)間(1,I)內(nèi)隨機(jī)產(chǎn)生一個(gè)整數(shù)r,并在區(qū)間(1,I)中隨機(jī)采樣r個(gè)互不相等的數(shù);2)按照步驟(2)產(chǎn)生的整數(shù)，將父代1和父代2中對(duì)應(yīng)整數(shù)位置的基因復(fù)制到子代1和子代2中;3)將父代1和父代2剩余的基因依次復(fù)制到子代2和子代1中，并保持位置與順序。

B種群機(jī)器部分交叉：同步概率比較的交叉方式如圖3。

圖3 機(jī)器部分交叉

1)隨機(jī)產(chǎn)生工序長(zhǎng)度個(gè)[0,1]之間的隨機(jī)數(shù)；2)記錄子代1、2中隨機(jī)數(shù)小于交叉概率的工序號(hào)；3)如果子代2中的工序號(hào)與子代1中交叉概率的工序號(hào)相同，就記錄下該子代2的順序位置,將該位置替換為父代2上相同位置的基因。

圖4所示為兩條父代染色體進(jìn)行工序機(jī)器對(duì)應(yīng)變異。1)在工序長(zhǎng)度的區(qū)間內(nèi)隨機(jī)產(chǎn)生兩個(gè)整數(shù)1,3；2)子代1復(fù)制父代2工序部分位置1和位置3的基因，機(jī)器部分同理；3)子代2復(fù)制父代1工序部分位置1和位置3的基因，機(jī)器部分同理。此種方式不隨機(jī)突變的原因是避免產(chǎn)生不屬于解集中的不可行解。

圖4 工序與機(jī)器的對(duì)應(yīng)變異

2.4 算法基本流程

多種群NSGA-II改進(jìn)算法，算法流程如圖5所示。

圖5 改進(jìn)多種群NSGA-Ⅱ的流程圖

3 算法性能測(cè)試

實(shí)驗(yàn)數(shù)據(jù)采用生成大規(guī)模數(shù)據(jù)集腳本產(chǎn)生3數(shù)據(jù)集集:100×10,100×30 ,100×50其中n×m表示n個(gè)工件m臺(tái)機(jī)器，為測(cè)試算法的有效性，本文將測(cè)試結(jié)果與傳統(tǒng)的NSGA-Ⅱ(NSGA-Ⅱ)以及單種群NSGA-Ⅱ改進(jìn)算法(INSGA-Ⅱ)結(jié)果進(jìn)行比較。將每種算法各自運(yùn)行10次結(jié)果進(jìn)行歸一化通過(guò)構(gòu)造評(píng)價(jià)函數(shù)Vi得到 10次結(jié)果中的的最優(yōu)解，設(shè)定權(quán)重值ω1,ω2,ω3仍為0.5,0.3,0.2，函數(shù)Vi如式(5)所示。式中ω1,ω2,ω3為目標(biāo)值f1,f2,f3的權(quán)重，f1max,f1min,f2max,f2min,f3max,f3min為算法運(yùn)行10次中指標(biāo)f1，f2，f3的最大值與最小值

(5)

算法的參數(shù)為：種群規(guī)模為100；迭代次數(shù)為100；交叉概率為0.8；變異概率為0.1。

記錄3種算法10次實(shí)驗(yàn)中的最小Vi值既最優(yōu)解。表1為NSGA-Ⅱ、INSGA-Ⅱ、IMNSGA-Ⅱ在3數(shù)據(jù)集上的對(duì)比結(jié)果。比較實(shí)驗(yàn)結(jié)果中評(píng)價(jià)函數(shù)F值，本文提出的多種群NSGA-Ⅱ改進(jìn)算法均優(yōu)于兩種對(duì)比算法，其中FJSP的最關(guān)鍵評(píng)價(jià)指標(biāo)最大完工時(shí)間f1在3個(gè)數(shù)據(jù)集中均領(lǐng)先對(duì)比算法。對(duì)比實(shí)驗(yàn)表明，本文提出的算法更適用于大規(guī)模FJSP并在大規(guī)模測(cè)試集上得到驗(yàn)證。

表1 不同數(shù)據(jù)集對(duì)比結(jié)果

4 結(jié)束語(yǔ)

依據(jù)實(shí)際車間生產(chǎn)對(duì)調(diào)度問(wèn)題的需要，構(gòu)建以最小化最大完工時(shí)間、最小化關(guān)鍵機(jī)器最大負(fù)荷、最小化總機(jī)器負(fù)荷為指標(biāo)的調(diào)度模型，來(lái)對(duì)車間生產(chǎn)過(guò)程進(jìn)行調(diào)度優(yōu)化。提出了多種群NSGA-II改進(jìn)算法，改進(jìn)其編碼與解碼、種群初始化、交叉和變異方式，并在種群初始化過(guò)程中使用多種群策略并在不同種群中使用不同的交叉方式，盡可能提升子代的差異化程度，避免算法“早熟”收斂。最后在生成的大規(guī)模數(shù)據(jù)集上驗(yàn)證了所提出算法的有效性與可行性。