陳自豪，陳松航，陳 豪

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

0 引 言

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

FJSP問題的一個(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ī)器可供選擇，接下來(1 2)，(3 4)分別表示工序1在機(jī)器1上加工用時(shí)為2，在第3臺(tái)機(jī)器上加工用時(shí)為4，以此類推[6]，直至結(jié)束。

根據(jù)上述數(shù)據(jù)特點(diǎn)，采用Python語法和關(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ù)(沒有第一行)

1.3 模型構(gòu)建

在求解FJSP的過程中，需要一些常用的指標(biāo)。根據(jù)工廠的實(shí)際需求，使用了3個(gè)貼近生產(chǎn)成本的指標(biāo)來構(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ī)器選擇問題會(huì)造成機(jī)器負(fù)荷不平衡，從而無法提高機(jī)器利用率而產(chǎn)生效率瓶頸。為克服由于調(diào)度方案不同而引發(fā)的機(jī)器負(fù)荷不平衡問題，也為提高每臺(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來構(gòu)造評(píng)價(jià)函數(shù)F如式(4)所示，使用評(píng)價(jià)函數(shù)F來評(píng)價(jià)算法在求解FJSP問題中所得到最優(yōu)解的優(yōu)劣

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

(4)

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

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

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

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

圖1 染色體編碼

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

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

通過實(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)行歸一化通過構(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é)束語

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