基于多群體協(xié)同進(jìn)化混合算法的FJSP研究*

歐陽森山，黃利福

(1.中航工業(yè)成都飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司，成都 610092；2.西北工業(yè)大學(xué) 管理學(xué)院，西安 710129)

基于多群體協(xié)同進(jìn)化混合算法的FJSP研究*

歐陽森山1，黃利福2

(1.中航工業(yè)成都飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司，成都 610092；2.西北工業(yè)大學(xué) 管理學(xué)院，西安 710129)

為更有效地解決柔性作業(yè)車間調(diào)度問題，提出一種多群體協(xié)同進(jìn)化混合算法，該混合算法的主群與子群分別采用帶有精英保留策略的遺傳算法與粒子群算法。算法初期主群與子群以不同的策略獨(dú)立并行地進(jìn)行尋優(yōu)，后期主群與子群、子群之間按照一定的規(guī)則進(jìn)行信息的交流以實(shí)現(xiàn)協(xié)同進(jìn)化，從而提高算法前期全局搜索能力與后期局部挖掘能力。此外，借助信息熵實(shí)現(xiàn)了主群交叉、變異概率的自適應(yīng)調(diào)整并運(yùn)用凹函數(shù)遞減策略對三個子群的慣性權(quán)重值進(jìn)行動態(tài)調(diào)整以提高該混合算法的整體優(yōu)化性能。最后，通過Kacem基準(zhǔn)問題驗(yàn)證了該算法求解柔性作業(yè)車間調(diào)度問題的有效性。

柔性作業(yè)車間調(diào)度；精英保留策略；信息熵；凹函數(shù)遞減策略

0 引言

進(jìn)入21世紀(jì)以來，新一輪科技革命和產(chǎn)業(yè)變革蓄勢待發(fā)，中國正在從“制造大國”向“制造強(qiáng)國”邁進(jìn)?！吨袊圃?025》明確指出“以推進(jìn)智能制造為主攻方向”，智能制造主要體現(xiàn)在“動態(tài)感知、實(shí)時分析、自主決策、精準(zhǔn)執(zhí)行”四個方面的特征，而其中“自主決策”是智能最直接體現(xiàn)，對于智能車間來說“自主決策”主要聚焦在柔性作業(yè)車間調(diào)度問題[1](Flexible Job-Shop Scheduling Problem，F(xiàn)JSP)。它是智能生產(chǎn)計(jì)劃管理的核心，同時也是生產(chǎn)管理領(lǐng)域中最為復(fù)雜的問題之一，具有動態(tài)隨機(jī)性、多約束性與多目標(biāo)性等特點(diǎn)。

目前，柔性作業(yè)車間調(diào)度問題的有效解決方法主要集中在遺傳算法[2-7]、粒子群算法[8-11]、蟻群算法[12-15]等智能優(yōu)化算法。不同算法求解柔性作業(yè)車間調(diào)度問題的優(yōu)化性能不同且均存在一定的缺陷，為此，眾多學(xué)者對相關(guān)算法進(jìn)行了一定的改進(jìn)。Mitsuo Gen等[3]提出一種帶有瓶頸轉(zhuǎn)移的多級遺傳算法?？罪w等[8]提出一種改進(jìn)的雙層粒子群優(yōu)化算法以解決FJSP。劉志勇等[14]對蟻群算法信息素更新規(guī)則進(jìn)行改進(jìn)，并將其應(yīng)用于解決多目標(biāo)柔性作業(yè)車間調(diào)度問題。本文在前人研究的基礎(chǔ)之上提出一種基于粒子群算法與遺傳算法的多群體協(xié)同進(jìn)化的混合優(yōu)化算法(Multi-Swarm Cooperative Genetic Algorithm-Particle Swarm Optimization，MCGA-PSO)，并以典型調(diào)度案例Kacem問題為例進(jìn)行仿真模擬與對比分析以驗(yàn)證其可行性與有效性。

1 問題描述與模型構(gòu)建

1.1 問題描述

柔性作業(yè)車間調(diào)度問題可描述為[5]：一個加工系統(tǒng)有n個待加工工件與m臺機(jī)器，每個工件包含一道或多道工序，工件的工序的加工順序是確定的；每道工序可在不同的機(jī)器上加工，且加工時間也不盡相同。調(diào)度的目標(biāo)是合理地分配機(jī)器并確定各工序的加工順序以使相應(yīng)的性能指標(biāo)得到優(yōu)化。此外，在加工過程中需要滿足以下約束條件[8]。

(1)同一工件的工序之間存在先后約束，不同工件的工序之間沒有先后約束；

(2)一臺機(jī)器同一時刻只能加工一個工件；

(3)每個工序在某一時刻只能被一臺機(jī)器加工；

(4)所有工件具有相同的優(yōu)先級；

(5)各工件在零時刻都可以被加工。

1.2 模型構(gòu)建

基于上述柔性作業(yè)車架調(diào)度問題的描述，可以建立其相應(yīng)的數(shù)學(xué)模型。模型建立過程中所涉及的符號含義如下：

n:工件數(shù)量；m:機(jī)器數(shù)量；Ji:工件集合中第i個工件；ci:工件Ji的完工時間；

vi:工件Ji包含的工序個數(shù)；pij:工件Ji的第j道工序；

sij:工序pij的開始加工時間；tijk工序pij在機(jī)器k上的加工時間；

Mij:工序pij可用的加工機(jī)器集合；mij:工序pij可用加工機(jī)器數(shù)；

Mk:機(jī)器集合Mij中的第k臺機(jī)器；L：一個足夠大的正數(shù)；

本文主要研究優(yōu)化目標(biāo)為最大完工時間的柔性作業(yè)車間調(diào)度問題，其所對應(yīng)的優(yōu)化模型可以表示為：

(1)

sij+xijh×tijh≤cij

(2)

(3)

(4)

(5)

Mk?Mij

(6)

(7)

其中：式(1)表示優(yōu)化目標(biāo)為最大完工時間最?。皇?2)與式(3)表示工件的各道工序之間的先后順序約束；式(4)和式(5)表示同一時刻一臺機(jī)器只能加工一個工件；式(6)表示某一工序只能由其可選機(jī)器集合中的機(jī)器加工；式(7)表示一道工序在某一時刻只能被一臺機(jī)器加工。

2 多群體協(xié)同進(jìn)化混合算法

2.1MCGA-PSO算法設(shè)計(jì)

在MCGA-PSO算法初期，各群體依照自身的進(jìn)化規(guī)則對整個搜索空間進(jìn)行獨(dú)立并行的搜索以提高算法初期的全局探索能力，后期主群與子群、子群之間按照一定的規(guī)則進(jìn)行信息交流，并以主群為主對搜索空間進(jìn)行深度的挖掘，從而使得算法的局部挖掘能力及收斂精度得到提高。此外，為了避免單一遺傳算法、粒子群算法易早熟收斂的缺陷，提高種群的多樣性，MCGA-PSO算法主群借助種群信息熵均值實(shí)現(xiàn)交叉概率與變異概率的自適應(yīng)調(diào)節(jié)，同時將凹函數(shù)遞減策略引入到3個子群中以實(shí)現(xiàn)慣性權(quán)重值的動態(tài)調(diào)整，并運(yùn)用精英策略保留進(jìn)化過程中的優(yōu)勢個體。MCGA-PSO算法的具體操作步驟如下所示：

步驟1：初始化主群與子群相關(guān)參數(shù)。

步驟2：分別計(jì)算主群與3個子群個體的適應(yīng)度值，并記錄進(jìn)化過程中產(chǎn)生的最優(yōu)個體。

步驟3：gen=gen+1，對主群中的個體進(jìn)行交叉與變異操作并更新子群粒子的位置與速度。

步驟4：判斷gen是否小于iter，若小于則返回步驟2。否則，執(zhí)行步驟5。

步驟5：計(jì)算主群與3個子群個體的適應(yīng)度值，并分別篩選出3個子群中的最優(yōu)粒子，并將其轉(zhuǎn)換之后替換主群中適應(yīng)度較差的個體。

步驟6：gen=gen+1，主群中的個體進(jìn)行交叉與變異操作并更新子群粒子的位置與速度。

步驟7：判斷gen是否小于maxgen，若小于則轉(zhuǎn)至步驟5。否則，輸出最優(yōu)解。

MCGA-PSO算法流程如圖1所示。

圖1 MCGA-PSO算法流程

2.2MCGA-PSO算法參數(shù)設(shè)計(jì)

(1)交叉概率與變異概率設(shè)計(jì)

遺傳算法中的交叉算子與變異算子對算法的收斂性具有關(guān)鍵性的影響，而在傳統(tǒng)遺傳算法搜索過程中它們的值是固定不變的，致使算法易陷入局部最優(yōu)解。因此，本文將信息熵融入MCGA-PSO算法中來衡量種群中個體的差異程度，并借助信息熵實(shí)現(xiàn)算法中的交叉概率Pc及變異概率Pm值的動態(tài)自適應(yīng)調(diào)整。

假設(shè)種群具有M個個體，每個個體由N個基因組成，設(shè)Rj是M個個體第j位基因值的集合，bij表示第i個個體第j位基因值在Rj中的重復(fù)數(shù)，Pij表示第i個個體第j位基因值在Rj中的所占比例。種群第j位基因的信息熵可通過下式計(jì)算得出[11]：

(8)

種群的多樣性可用種群所有基因位的平均信息熵H來衡量：

(9)

主群的自適應(yīng)交叉概率Pc與自適應(yīng)變異概率Pm分別為：

(10)

(11)

其中，Pc1與Pc2分別為最大與最小交叉概率，Pm1與Pm2分別為最大與最小變異概率。

(2)慣性權(quán)重設(shè)計(jì)

粒子群算法中的粒子通過不斷追尋個體極值及群體極值進(jìn)行全局最優(yōu)搜索。搜索過程中，各粒子依據(jù)群體極值與個體極值粒子的位置不斷更新自身的速度及位置，其速度與位置的更新公式如下：

(12)

(13)

慣性權(quán)重ω表明粒子當(dāng)前速度受歷史速度的影響程度，它可以有效的平衡算法的全局探索能力與局部挖掘能力，提高算法的優(yōu)化性能。在本文所提的MCGA-PSO算法中，3個子群的慣性權(quán)重值采用凹函數(shù)遞減的策略進(jìn)行調(diào)節(jié)，以使算法的優(yōu)化性能得到提高。

(14)

公式(14)中，t為當(dāng)前進(jìn)化代數(shù)；tmax為最大的進(jìn)化代數(shù)；ωmax與ωmin分別代表ω的最大值與最小值。

2.3 編碼

由于FJSP不僅需要確定工序的加工順序，還要解決各工序的機(jī)器分配問題，基于工序的編碼方式已不能滿足其需要，本文采用分段式的編碼方式，該編碼包括工序的排序機(jī)器的選擇兩部分。

工序排序部分：每一基因代表一個工序，同一工件的工序用相應(yīng)的工件號表示，并且同一工件序號出現(xiàn)的次數(shù)與該工件的工序總數(shù)相等，其出現(xiàn)的第k次表示該工件的第k道工序。

機(jī)器選擇部分：機(jī)器選擇部分的基因?qū)?yīng)的數(shù)字表示該工序的可選加工機(jī)器集合中相應(yīng)的機(jī)器序號。

圖2為一個編碼案例，前半部分表示工序的排序，后半部分為機(jī)器的選擇。

圖2 分段式編碼方式

如工序排序部分的第一個數(shù)字為2，且數(shù)字2第一次出現(xiàn)，則它表示工件J2的第1道工序，第4基因位上的數(shù)字2表示工件J2的第2道工序，以此類推。在機(jī)器選擇部分，如工序O11的可選加工機(jī)器集中有三臺機(jī)器，則該基因位對應(yīng)的數(shù)字3表示可選機(jī)器集合中的第3臺機(jī)器，即機(jī)器M3。

2.4 位置與速度的更新

工序排序部分的迭代更新：由于粒子群算法對應(yīng)的是連續(xù)空間而柔性作業(yè)車間調(diào)度則屬于離散空間優(yōu)化問題，所以在實(shí)現(xiàn)速度與位置的更新之后需要對其進(jìn)行適當(dāng)?shù)恼{(diào)整以滿足問題的需要。具體操作如圖3所示。

圖3 工序排序部分更新

機(jī)器選擇部分的迭代更新：在工序排序部分完成更新之后，機(jī)器選擇部分各位置根據(jù)其所對應(yīng)的工序進(jìn)行更新，其數(shù)值為介于[1,m]之間的隨機(jī)整數(shù)值，m代表該工序可選機(jī)器數(shù)。

2.5 遺傳算法操作

(1)選擇操作

選擇操作是MCGA-PSO算法中的一個關(guān)鍵操作，本文采用根據(jù)個體適應(yīng)度值對種群中的個體進(jìn)行優(yōu)勝劣汰的輪盤賭選擇策略，其選擇概率公式如公式(15)所示：

(15)

其中：P(xi)為個體xi的選擇概率，f(xi)為個體xi的適應(yīng)度值。

(2)交叉操作

本文采用張超勇等[7]所提出的POX交叉方式實(shí)現(xiàn)工序排序部分的交叉，機(jī)器選擇部分采用多點(diǎn)的交叉方式。

工序POX交叉方式步驟如下：

1)隨機(jī)劃分工件集{1，2，…，m}為兩個非空子集J1和J2；

2)將Parent1與Parent2中包含在J1集合中的工件號分別復(fù)制到Children1與Children2；

3)將Parent2中包含在J2的工件號依次復(fù)制到Children1，將Parent1中包含在J2的工件號依次復(fù)制到Children2。

POX交叉方式具體操作過程如圖4所示。

圖4 POX交叉

機(jī)器多點(diǎn)交叉方式如圖5所示，首先隨機(jī)產(chǎn)生一個由0、1組成且長度為工序總數(shù)的rand0&1集合，而后互換兩個父代0位置的基因，1位置的基因保持不變。

圖5 多點(diǎn)交叉方式

(3)變異操作

遺傳算法解決柔性作業(yè)車間調(diào)度問題時常使用的變異算子有插入變異、逆轉(zhuǎn)變異和交換變異等。針對柔性作業(yè)車間調(diào)度問題的特點(diǎn)，本文采用兩種不同的變異操作分別實(shí)現(xiàn)工序排序與機(jī)器選擇兩部分的變異。工序排序部分采用交換變異的方法，即隨機(jī)選擇兩個工件的工序(基因)而后調(diào)換這兩個基因，各工序所選擇的機(jī)器不變。機(jī)器選擇部分采取兩點(diǎn)變異的方法，首先隨機(jī)選取機(jī)器選擇部分的兩個基因，而后在各基因所對應(yīng)工序的可選機(jī)器集合中隨機(jī)選擇一臺機(jī)器替換原機(jī)器。

3 實(shí)例仿真與結(jié)果分析

為驗(yàn)證MCGA-PSO算法求解FJSP問題的有效性，本文選取典型調(diào)度案例Kacem基準(zhǔn)問題[16]中的8×8部分柔性調(diào)度問題與10×10的全部柔性調(diào)度問題進(jìn)行測試。通過Matlab7.0編程實(shí)現(xiàn)MCGA-PSO算法的具體應(yīng)用，MCGA-PSO算法的主要參數(shù)設(shè)置如下：主群數(shù)P=1，子群數(shù)Q=3，各種群個體數(shù)psize=100，iter=400，maxgen=600，Pc1=0.8，Pc2=0.1，Pm1=0.3，Pm2=0.1，ωmax=0.9，ωmin=0.1，c1=c2=1.5，每個實(shí)例獨(dú)立運(yùn)行10次。

表1給出了MCGA-SPO算法求解Kacem基準(zhǔn)問題的結(jié)果，同時與其它算法的運(yùn)行結(jié)果進(jìn)行對比以驗(yàn)證該算法的性能。MCGA-PSO算法求解Kacem問題的收斂曲線與最優(yōu)解甘特圖如圖6～圖9所示。

表1 Kacem基準(zhǔn)問題測試結(jié)果比較

由表1可以看出MCGA-PSO算法求解Kacem基準(zhǔn)問題所得的最優(yōu)解均已達(dá)到參考文獻(xiàn)中的最優(yōu)值，且從其收斂曲線圖可以看出該算法在求解柔性作業(yè)車間調(diào)度問題時具有較好的收斂精度與收斂速度，驗(yàn)證了該算法的有效性。

圖6 8×8 Kacem問題

圖7 10×10 Kacem問題

4 結(jié)論

針對柔性作業(yè)車間調(diào)度問題的特點(diǎn)，本文在粒子群算法與遺傳算法的基礎(chǔ)上，提出一種多群體混合優(yōu)化算法，并對算法相關(guān)參數(shù)進(jìn)行了詳細(xì)設(shè)計(jì)。該混合算法分為獨(dú)立并行進(jìn)化與協(xié)同進(jìn)化兩個階段，大幅增強(qiáng)了算法的全局搜索能力與局部挖掘能力，能夠有效地避免單一粒子群算法與遺傳算法易陷入早熟收斂的缺陷。最后，基于Kacem實(shí)例的仿真實(shí)驗(yàn)表明該算法能夠有效地應(yīng)用于解決柔性作業(yè)車間調(diào)度問題。

[1] 石小秋,石宇強(qiáng),袁雪嬌. 離散多種群入侵雜草優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題[J]. 信息與控制,2015,44(2):238-243.

[2] 劉瓊,張超勇,饒運(yùn)清,等. 改進(jìn)遺傳算法解決柔性作業(yè)車間調(diào)度問題[J]. 工業(yè)工程與管理,2009,14(2):59-66.

[3] Gen M, Jie G, Lin L. Multistage-Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem[J]. Studies in Computational Intelligence, 2009:183-196.

[4] Giovanni L D, Pezzella F. An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem[J]. European Journal of Operational Research, 2010, 200(2):395-408.

[5] 張超勇,饒運(yùn)清,李培根,等. 柔性作業(yè)車間調(diào)度問題的兩級遺傳算法[J]. 機(jī)械工程學(xué)報,2007,43(4):119-124.[6] ZHANG Guohui. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2009, 45(7):145-151.

[7] 張超勇,饒運(yùn)清,劉向軍,等. 基于POX交叉的遺傳算法求解Job-Shop調(diào)度問題[J]. 中國機(jī)械工程,2004,15(23):2149-2153.

[8] 孔飛,吳定會,紀(jì)志成. 基于雙層粒子群優(yōu)化算法的柔性作業(yè)車間調(diào)度優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用,2015,35(2):476-480.

[9] Lim W H, Isa N A M. An adaptive two-layer particle swarm optimization with elitist learning strategy[J]. Information Sciences, 2014, 273: 49-72.

[10] 宋存利. 求解柔性作業(yè)調(diào)度問題的協(xié)同進(jìn)化粒子群算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2013,49(21):15-18.

[11] 黃英杰,姚錫凡,古耀達(dá). 基于熵的混合粒子群算法在柔性調(diào)度中的應(yīng)用[J]. 湖南大學(xué)學(xué)報(自然科學(xué)版),2012,39(3):48-52.

[12] Huang R H, Yang C L, Cheng W C. Flexible job shop scheduling with due window—a two-pheromone ant colony approach[J]. International Journal of Production Economics, 2013, 141(2): 685-697.

[13] Rossi A, Dini G. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method[J]. Robotics and Computer-Integrated Manufacturing, 2007, 23(5): 503-516.

[14] 劉志勇,呂文閣,謝慶華,等. 應(yīng)用改進(jìn)蟻群算法求解柔性作業(yè)車間調(diào)度問題[J]. 工業(yè)工程與管理,2010,15(3):115-119.

[15] 薛宏全,魏生民,張鵬,等. 基于多種群蟻群算法的柔性作業(yè)車間調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用,2013,49(24):243-248,261.

[16] Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems [J].IEEE Transactions on systems,Man and Cybernetics:Part C,2002,32(1):1-13.

[17] 董蓉,何衛(wèi)平. 求解FJSP的混合遺傳—蟻群算法[J]. 計(jì)算機(jī)集成制造系統(tǒng),2012,18(11):2492-2501.

(編輯 李秀敏)

Flexible Job-shop Scheduling Study Based On Multi-swarm Cooperative Hybrid Algorithm

OUYANG Sen-shan1，HUANG Li-fu2

(1.Chengdu Aircraft Industrial (Group) Co., Ltd, Chengdu 610092,China；2. School of Management, Northwestern Polytechnical University,Xi’an 710129, China)

In order to solve flexible job-shop scheduling problem more efficiently, a new multi-swarm cooperative hybrid algorithm is proposed in this paper, genetic algorithm with elite strategy and particle swarm algorithm were utilized in the master swarm and slave swarms respectively. In order to improve the global search ability of the proposed algorithm, parallel optimization calculation was performed in the master swarm and the slave swarms at the early stage. At the later stage of the algorithm, the master swarm and slave swarms share information according to certain rules to enhance the local search ability and optimization accuracy of the proposed algorithm. Besides, in order to improve the overall optimization performance of this hybrid algorithm, crossover probability and mutation probability were adjusted adaptively according to population information entropy and concave function decreasing strategy was adopted in the inertia factor. Finally simulation results on benchmark Kacem instance demonstrate the effectiveness of the proposed algorithm.

flexible job-shop scheduling problem; elitist strategy ;information entropy; concave function decreasing strategy

1001-2265(2017)01-0023-05

10.13462/j.cnki.mmtamt.2017.01.007

2016-04-13；

2016-04-27

國家自然科學(xué)基金項(xiàng)目(U1404702)

歐陽森山(1982—)，男，四川彭州人，中航工業(yè)成都飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司工程師，碩士，研究方向?yàn)檐囬g調(diào)度優(yōu)化，(E-mail)1465527151@qq.com；通訊作者：黃利福(1991—)，男，河南蘭考人，西北工業(yè)大學(xué)碩士研究生，研究方向?yàn)檐囬g調(diào)度優(yōu)化，(E-mail)1036205547@qq.com。

TH166;TG506

A