（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070）

0 引言

車間調(diào)度效率的高低將直接影響產(chǎn)品的生命周期和企業(yè)的利益成本。1919年，由Gantt[1]率先使用甘特圖表示車間調(diào)度的作業(yè)流程；1976年，Garey[2]等證明了該類組合優(yōu)化問題屬于NP完全問題；1998年，Egon[12]等從調(diào)度解鄰居角度出發(fā)，提出的N6結(jié)構(gòu)大大減少了在關(guān)鍵路徑上做無效搜索的次數(shù)，減少了搜索時(shí)間同時(shí)保證了解的質(zhì)量。由于作業(yè)車間調(diào)度問題較旅行商問題等其他NP問題更為復(fù)雜[14]，幾十年來，求解該類問題的方法大多集中在非數(shù)值近似算法上，該近似算法大多為生物進(jìn)化算法，分別有模擬退火算法[3]，遺傳算法[4]，例子群算法[5]，禁忌搜索算法[6]，以及各類改進(jìn)的生物進(jìn)化算法和混合算法。例如，粒子群算法具有更新規(guī)則簡單，編碼易于實(shí)現(xiàn)且具有較快的收斂性等優(yōu)點(diǎn)[7]，遺傳算法和模擬退火算法具有搜索全局最優(yōu)解的優(yōu)點(diǎn)[8]。因此Min[9]等運(yùn)用自適應(yīng)的變異概率與全局退火的策略，提出遺傳退火算法；李小濤[10]等提出基于染色體agent的鄰居結(jié)構(gòu)，結(jié)合模擬退火遺傳混合算法求解車間調(diào)度問題。近年來，隨著人工智能技術(shù)的興起，Bagheri[15]等提出的人工免疫算法在和Wang[16]等提出的人工蜂群算法在求解作業(yè)車間調(diào)度問題上開始受到重視，求解精度質(zhì)量大幅度提高。

隨著車間調(diào)度問題的規(guī)模增大，求解該問題的難度和時(shí)間也將呈指數(shù)級(jí)別增加[2]，針對文獻(xiàn)[9,10,15,16]在收斂性和計(jì)算時(shí)間上的不足，文中結(jié)合粒子群算法收斂性快的優(yōu)點(diǎn)，提出粒子群遺傳混合算法。本文的混合算法首先為了跳出車間調(diào)度問題解的大山谷結(jié)構(gòu)[10]，提出以模擬退火操作中使用的Metropolis準(zhǔn)則定義自適應(yīng)的變異概率[9]，混合算法中再整合粒子群算法在局部鄰域搜索最優(yōu)解的優(yōu)點(diǎn)，將該局部最優(yōu)調(diào)度解作為染色體變異交叉的對象，在變異和交叉操作中再輔以改進(jìn)的2變換鄰域搜索[11]。最后仿真實(shí)例說明了該混合算法具有有效性和可行性的優(yōu)點(diǎn)。

1 生產(chǎn)作業(yè)車間調(diào)度問題模型

1.1 生產(chǎn)作業(yè)車間調(diào)度系統(tǒng)描述

Egon[12]等提出作業(yè)車間調(diào)度問題是求解所有工件的所有工序在指定調(diào)度安排下最大完工時(shí)間最小值的過程。生產(chǎn)作業(yè)車間調(diào)度問題的已知輸入條件有：加工機(jī)器集合工件集合工序集合工件pi的工序集合為工件加工時(shí)間集合工件pi的工序加工時(shí)間集合

由于生產(chǎn)作業(yè)車間調(diào)度問題需要同時(shí)考慮工件的加工時(shí)間和加工順序，因此增加了求解此類組合優(yōu)化問題的復(fù)雜性；且在實(shí)際生產(chǎn)調(diào)度中，需要考慮資源數(shù)量和設(shè)備容量等約束，同時(shí)該離散系統(tǒng)需要從離散問題優(yōu)化角度入手。因此求解大規(guī)模生產(chǎn)作業(yè)車間調(diào)度問題將增加時(shí)間和空間消耗。本文在求解此類問題過程做出以下五點(diǎn)假定：

1）已知每個(gè)工件的每道工序在指定機(jī)器上加工；

2）已知每個(gè)工件的每道工序的加工時(shí)間，且為常數(shù)；

3）每個(gè)工件的工序加工順序不能改變，即必須在前一道工序加工完成之后才能完成后一道工序，而對于不同工件的加工工序順序沒有順序要求；

4）每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件的一道工序，且機(jī)器在執(zhí)行加工任務(wù)時(shí)不會(huì)發(fā)生故障；

5）機(jī)器加工工件沒有時(shí)間等待，且每個(gè)工件只在機(jī)器上加工一次。

1.2 數(shù)學(xué)模型表達(dá)式

作業(yè)車間調(diào)度問題要求最大完工時(shí)間（makespan）[12]最小，因此結(jié)合模型假定，提出以下數(shù)學(xué)模型：

目標(biāo)函數(shù)為式(1)：

目標(biāo)函數(shù)式(1)表示所有工件的所有工序在指定調(diào)度順序下最大加工時(shí)間最短，其中ei,j,m(i,j)表示第i個(gè)工件的第j道工序在第m臺(tái)機(jī)器上加工的結(jié)束時(shí)間；

約束條件為式(2)～式(5)：

式(2)為每個(gè)工件每道工序的結(jié)束加工時(shí)刻等于開始加工時(shí)刻加上對應(yīng)工序的加工時(shí)間，其中si,j,m(i,j)表示第i個(gè)工件的第j道工序在第m臺(tái)機(jī)器上加工的開始時(shí)間，Ti,j,m(i,j)表示第i個(gè)工件的第j道工序在第m臺(tái)機(jī)器上加工的加工時(shí)間；

式(3)是每個(gè)工件前后加工順序的約束條件，即每個(gè)工件后一道工序開始時(shí)間應(yīng)大于該工件前一道工序的結(jié)束時(shí)間；

式(4)、式(5)是每臺(tái)機(jī)器的約束條件，保證每一臺(tái)機(jī)器上同一時(shí)刻只能加工一個(gè)工件的一道工序；

M表示一個(gè)無窮大的常數(shù)。

車間調(diào)度問題是一個(gè)典型的多約束優(yōu)化組合問題，已經(jīng)證明此問題屬于NP完全問題，該類問題需要在現(xiàn)有調(diào)度解空間中迭代搜尋得到最優(yōu)解。即使求解規(guī)模較小，求解質(zhì)量與效率也都很難得到保證，為提高該類問題解的質(zhì)量與搜索效率，本文采用改進(jìn)的粒子群遺傳混合進(jìn)化算法，從而讓總體目標(biāo)函數(shù)達(dá)到最優(yōu)。

2 基于自適應(yīng)變異概率的PSO與GA混合算法尋優(yōu)

2.1 個(gè)體編碼方式

本混合算法采用基于工序的編碼方式，每個(gè)個(gè)體均對應(yīng)于一種調(diào)度方案。以n個(gè)工件，每個(gè)工件有m道工序?yàn)槔?，在該編碼方式中，每個(gè)工件i出現(xiàn)m次，從前往后依次表示工件i的加工順序。以3×3為例，參照表1的工序加工機(jī)器順序，工序[1,3,2,1,2,3,2,1,3]中，第一個(gè)1表示工件1的第一道工序在機(jī)器2上加工，第二個(gè)1表示工件1的第二道工序在機(jī)器3上加工，第三個(gè)1表示工件1的第三道工序在機(jī)器1上加工。

表1 每個(gè)工件每道工序的加工機(jī)器

2.2 混合算法目標(biāo)值定義

粒子群算法搜尋得到的局部最優(yōu)解和遺傳算法的適應(yīng)值均對應(yīng)指定調(diào)度下工件總完工時(shí)間，且應(yīng)保證總完工時(shí)間最短。

2.3 PSO-GA混合算法操作思想

1）在遺傳算法變異概率選擇上，參照模擬退火中Metropolics[9]準(zhǔn)則選擇適當(dāng)?shù)淖儺惛怕?，對交叉概率也需進(jìn)行概率線性變換。

2）將粒子群算法尋求的局部最優(yōu)調(diào)度解作為變異和交叉操作的對象，根據(jù)粒子群慣性權(quán)重w特點(diǎn)[13]，當(dāng)w過大，粒子群偏向全局搜尋，而當(dāng)w較小，粒子群偏向于局部搜尋，因此本混合算法對慣性權(quán)重w進(jìn)行自適應(yīng)計(jì)算。

3）對2變換鄰域鄰居結(jié)構(gòu)進(jìn)行改進(jìn)。變異操作中，在1，2中隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)n，如果n=1，則變異位a,b之間的距離小于整條染色體的三分之一，將a,b兩處的基因?qū)φ{(diào)；如果n=2，則變異位a,b之間的距離沒有限制，再將a,b兩處的基因?qū)φ{(diào)。交叉操作中，同樣在1，2中隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)n，如果n=1，則交叉位a,b之間的距離小于整條染色體的三分之一，參與交叉的兩染色體中從左往右，先將a,b之間基因相同的標(biāo)記為0，并參與交叉操作，不為0的不參與交叉操作；如果n=2，則交叉位a,b之間的距離沒有限制，按同樣的方法即可實(shí)現(xiàn)交叉操作。

2.4 自適應(yīng)變異概率計(jì)算

混合算法初期，為了加快個(gè)體變異，初期設(shè)置的變異概率pm較大[9]；隨著個(gè)體適應(yīng)度增加，以及為了加快計(jì)算速度，賦以變異概率自適應(yīng)值，具體如下所示：

上式中η為常數(shù)，設(shè)為2，k為進(jìn)化代數(shù)。

2.5 慣性權(quán)重自適應(yīng)計(jì)算

將慣性權(quán)重設(shè)置為變量，有利于擴(kuò)大對解空間的搜索，同時(shí)防止出現(xiàn)早熟的現(xiàn)象[13]。

式中wmax為最大慣性權(quán)重，wmin為最小慣性權(quán)重，itermax為總進(jìn)化代數(shù)，k為第k次進(jìn)化。

2.6 改進(jìn)2變換鄰域鄰居結(jié)構(gòu)圖例

1）以3*3的一個(gè)調(diào)度解作為例子，如圖1所示，一條染色體編碼為[3 1 2 3 1 2 1 2 3]。當(dāng)隨機(jī)產(chǎn)生的數(shù)值為2時(shí)，即發(fā)生變異的兩個(gè)位置之間距離應(yīng)沒有限制，變異位置為2和6，將染色體上兩變異位置對應(yīng)的基因互換位置后即可得到新的染色體，新染色體對應(yīng)的基因?yàn)閇3 2 2 3 1 1 1 2 3]。

圖1 當(dāng)n=2時(shí)的變異操作

2）以3*3為例，選取兩染色體分別為[3 1 2 3 1 1 2 3 2]和[1 2 2 3 1 3 1 2 3]，具體如圖2所示，隨機(jī)產(chǎn)生的交叉位置為2，即參與交叉兩染色體交叉位置之間的距離沒有限制，交叉位置分別為4和7。將兩染色體從4位到7位從左往右將相同的基因先后置為0，處理后的兩染色體基因分別為[3 1 2 0 0 0 2 3 2]和[1 2 2 0 0 3 0 2 3]，兩染色體中基因?yàn)?位置處的原基因再參與交叉操作，交叉后的新染色體分別為[3 1 2 1 1 3 2 3 2]和[1 2 2 1 1 3 3 2 3]。

圖2 當(dāng)n=2時(shí)的交叉操作

3 仿真算例

仿真工具：Matlab R2014a；

仿真環(huán)境：win10操作系統(tǒng)；cpu：i5-6200u處理器，2.3GHz；12GDDR4內(nèi)存。

3.1 參數(shù)設(shè)置

本混合算法種群大小為100，進(jìn)化代數(shù)設(shè)置為100，pm為0.1，wmax為1.2，wmin為0.4。

3.2 測試結(jié)果分析評(píng)價(jià)

圖3 算法流程圖

通過對6組測試數(shù)據(jù)進(jìn)行計(jì)算，且每組數(shù)據(jù)均進(jìn)行10次運(yùn)算，對最優(yōu)解與時(shí)間分別取平均值后得到表2。

通過與測試數(shù)據(jù)[14]進(jìn)行比對，混合算法得到的最優(yōu)解與目前已知的最優(yōu)解的平均誤差分別為：0%，1.2%，3.7%，3.9%，4.9%，3.9%。

同時(shí)，混合算法得到最優(yōu)解時(shí)間較目前得到已知最優(yōu)解時(shí)間有大幅度提升。

表2 混合算法與最優(yōu)解數(shù)值、時(shí)間對比

以FT10類測試問題為例，繪出混合算法迭代次數(shù)與最優(yōu)解的關(guān)系曲線圖如圖4所示。

由圖4可以看出，混合算法收斂速度快，用時(shí)短，F(xiàn)T10類測試問題在17代就達(dá)到滿意值，并且滿足精度要求。

圖4 FT10類混合算法仿真實(shí)例

為進(jìn)一步論證該混合算法的有效性，將該混合算法得到的解與普通的粒子群算法與模擬退火算法得到的解進(jìn)行對比，具體數(shù)值如表3所示。通過對比發(fā)現(xiàn)，混合算法得到的解均大幅度優(yōu)于普通的粒子群算法和模擬退火算法得到的解。

表3 混合算法與PSO,SA對比

以FT10為例，在迭代次數(shù)為2000條件下，將粒子群算法和模擬退火算法的迭代次數(shù)與最優(yōu)解的關(guān)系曲線圖繪出，如圖5所示?？梢钥吹狡胀≒SO與SA收斂速度較混合算法更慢，PSO需要在1087代才能收斂，SA需要在1291代才能收斂，且PSO得到的解1142和SA得到的解1101較混合算法得到的解957更差，且精度更低。

圖5 FT10類SA,PSO仿真實(shí)例

4 結(jié)論

通過參考模擬退火操作中Metropolics準(zhǔn)則定義自適應(yīng)的變異概率，很好地解決了車間調(diào)度問題解的大山谷結(jié)構(gòu)的問題，從而可以讓解跳出局部最優(yōu)；同時(shí)定義自適應(yīng)的慣性權(quán)重值，使得粒子群得到的局部最優(yōu)解向全局最優(yōu)解靠攏；得到的局部最優(yōu)解在變異交叉中輔以改進(jìn)的2變換鄰域操作，進(jìn)而充分體現(xiàn)了優(yōu)化算法中解的擴(kuò)散策略。

通過與3類6組經(jīng)典測試數(shù)據(jù)已知的最優(yōu)解進(jìn)行比對可以發(fā)現(xiàn)，本混合算法得到最優(yōu)解與目前已知的最優(yōu)解平均誤差均在5%以內(nèi)，且計(jì)算時(shí)間有大幅度提升；同時(shí)混合算法得到的最優(yōu)解與普通的粒子群算法和模擬退火算法得到的最優(yōu)解進(jìn)行對比可以發(fā)現(xiàn)，混合算法的最優(yōu)解具有明顯的優(yōu)勢。前后兩次仿真結(jié)果對照均論證了該粒子群遺傳混合算法具有有效性和可行性的優(yōu)點(diǎn)。

[1]A.S. Jain,S.Meeran. Deterministic job-shop scheduling: Past,present and future[J].European of Operational Research,113,1999.390-400.

[2]Garey M.R., Johnson D.S.,Sethi R. The complexity of flow shop and job-shop scheduling[J].Mathematics of Operation Research,1976,1(2).117-129.

[3]Van Laarhoven P.J.M., Aarts E.H.L.,Lenstra J.K. Job shop scheduling by simulated annealing[J].Operation Research,1992,40(1).113-125.

[4]Yamada T.,Nakano R.A genetic algorithm with multi-step crossover for job-shop scheduling problems[J]. Proceedings of Int.Conf. on GAs in Eng. Sys.,1995b.146-151.

[5]Sha D.Y.,& Lin H.H. A multi-objective PSO for job-shop scheduling problems[J].Expert System with Applications,2010,37(2).1065-1070.

[6]Nowicki E., Smutnicki C.A fast taboo search algorithm for the job-shop problem[J]. Management Science,1996,42(6).797-813.

[7]Wer-Der Chang.A modified particle swarm optimization with multiple subpopulations for multimodal function optimization problems[J].Applied Soft Computing,2015(33).170-173.

[8]Maniezzo V.Genetic evolution of the topology and weight distribution of neural network[J].IEEE Transactions on Neural Networks,1994,5(1).54-65.

[9]Min Liu,Zhi-jiang Sun,Jun-wei Yan, Jiong-song Kang.An adaptive annealing genetic algorithm for the job-shop planning and scheduling problem[J].Expert Systems with Application,2011,38.9248-9254.

[10]李小濤,彭翀.基于混合多智能體遺傳算法的作業(yè)車間調(diào)度問題研究[J].北京航空航天大學(xué)學(xué)報(bào),2017,43(2).410-416.

[11]趙良輝,鄧飛其.用于作業(yè)車間調(diào)度的模擬退火算法[J].制造業(yè)自動(dòng)化,2006,28(3).10-12.

[12]Egon Balas, Alkis Vazacopoulos. Guided local search with shifting bottleneck for job shop scheduling[J].Management Science,1998,44(2).262-270.

[13]Yannis Marinakis, Athanasios Migdalas, Angelo Sifaleras. A hybrid particle swarm optimization – variable neighborhood search algorithm for constrained shortest path problems[J].European of Operational Research, 2017,261.819-823.

[14]王凌.車間調(diào)度及其遺傳算法[M].清華大學(xué)出版社,2003,56-67.

[15]Bagheri, A., Zandieh, M., Mahdavi, I., Yazdani, M. An artificial immune algorithm for the flexible jos-shop scheduling problem[J].Future Generation Computer Systems,2010,26(4).533-540.

[16]Wang, L., Zhou, G., Xu, Y., Wang, S., Liu, M. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J].The international Journal of Advanced Manufacturing Technology,2011.1-13.