求解可重入作業(yè)車間調(diào)度問(wèn)題的改進(jìn)離散微粒群優(yōu)化算法

萬(wàn)婧

(山東省科學(xué)院海洋儀器儀表研究所，山東省海洋儀器儀表科技中心，山東 青島 26600)

求解可重入作業(yè)車間調(diào)度問(wèn)題的改進(jìn)離散微粒群優(yōu)化算法

萬(wàn)婧

(山東省科學(xué)院海洋儀器儀表研究所，山東省海洋儀器儀表科技中心，山東 青島 26600)

本文針對(duì)可重入作業(yè)車間調(diào)度問(wèn)題，對(duì)離散微粒群算法的搜索方式進(jìn)行改進(jìn)，混合一種變異機(jī)制，并結(jié)合Interchange鄰域局部搜索機(jī)制，設(shè)計(jì)與開(kāi)發(fā)有效的混合離散微粒群算法。通過(guò)實(shí)驗(yàn)仿真結(jié)果的比較，有力地證明了所提算法的有效性。

離散微粒群算法；局部搜索；作業(yè)車間

可重入作業(yè)車間調(diào)度問(wèn)題(reentrant job shop scheduling problem，RJSP)是工業(yè)生產(chǎn)中的典型調(diào)度問(wèn)題，是現(xiàn)代很多實(shí)際生產(chǎn)調(diào)度問(wèn)題的簡(jiǎn)化模型，包括諸如半導(dǎo)體生產(chǎn)、超大規(guī)模集成電路設(shè)計(jì)與制造、物流運(yùn)輸、網(wǎng)絡(luò)通信電路設(shè)計(jì)、電氣布線等問(wèn)題?？芍厝胱鳂I(yè)車間調(diào)度問(wèn)題的求解難度很高，一直是學(xué)術(shù)界和工程界共同關(guān)注的重要課題。除混合的算法開(kāi)發(fā)外，設(shè)計(jì)新穎的調(diào)度技術(shù)或?qū)⑵渌I(lǐng)域的優(yōu)化算法推廣到生產(chǎn)調(diào)度問(wèn)題中同樣是值得關(guān)注的課題。

1 問(wèn)題模型

可重入作業(yè)車間調(diào)度問(wèn)題通常描述如下：每個(gè)工件i在m臺(tái)機(jī)器上要被加工R(i)次，R(i)是可變的；所有工件經(jīng)過(guò)機(jī)器的順序都是恒定的；任何時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件，每個(gè)工件也只能在一臺(tái)機(jī)器上進(jìn)行加工。

C(πj,1,l(πj))=max{C(πj-1,1,l(πj-1)),C(πj,m,l(πj)-1)}+p(πj,1,l(πj)),j=1,…,R,

C(πj,k,l(πj))= max{C(πj-1,k,l(πj-1)),C(πj,k-1,l(πj))}+p(πj,k,l(πj)),k=2,…,m,

Cmax(π)=C(πR,m,l(πR)),

π*=arg{Cmax(π)}→min,

式中：m表示機(jī)器數(shù)，R表示n個(gè)工件中每個(gè)工件的重入次數(shù)，n表示工件數(shù)，π=[π1,π2,…,πR]是工件加工排序，πj∈{1,…,n}(j=1,…,R)表示排序π中第j個(gè)位置的工件，l(πj)表示工件πj在[π1,…,πj]中重復(fù)出現(xiàn)的次數(shù)，p(πj,k,l(πj)是工件πj第l(πj)次進(jìn)入第k臺(tái)機(jī)器的加工時(shí)間，C(πj,k,l(πj))是工件πj第l(πj)次進(jìn)入第k臺(tái)機(jī)器的完工時(shí)間，C(π0,k,l(π0))=0，C(πj,k,0)=0，k∈{1,…,m}，優(yōu)化目標(biāo)是找到一個(gè)最優(yōu)排序π*，使得對(duì)應(yīng)的最早完工時(shí)間Cmax最小。

2 研究方法

針對(duì)可重入作業(yè)車間調(diào)度問(wèn)題的求解方法，通常可分為精確方法、構(gòu)造性方法、改進(jìn)型方法和神經(jīng)網(wǎng)絡(luò)等。精確方法，如枚舉法[1]、分支定界法[2]、動(dòng)態(tài)規(guī)劃[3]等，由于其計(jì)算存儲(chǔ)量太過(guò)巨大，因此僅適用于求解小型種群規(guī)模問(wèn)題。構(gòu)造性方法通過(guò)一定的規(guī)則來(lái)構(gòu)造問(wèn)題的解，如Gupta法[4]、CDS法[5]、RA法、NEH法[6]、SL法等，此類求解方法可以快速尋找解的位置，以最快的速度找到最優(yōu)解，但通常解的質(zhì)量不優(yōu)。改進(jìn)型算法則是從若干已知解出發(fā)，對(duì)其周圍鄰域的不斷深入探索，以及對(duì)當(dāng)前解的替換來(lái)改進(jìn)解的質(zhì)量，如遺傳算法[7]、模擬退火[8]、進(jìn)化規(guī)劃[9]、禁忌搜索[10]等。這些方法的優(yōu)化效果十分可觀，但不足之處在于，需要大量迭代，并且其算法操作順序、參數(shù)和搜索結(jié)構(gòu)要求十分嚴(yán)格，均需謹(jǐn)慎選取。

微粒群算法[11]是一種基于進(jìn)化群體智能技術(shù)的新型算法，能夠通過(guò)模仿鳥類的覓食行為，尋求最優(yōu)解的過(guò)程就是鳥類覓食的過(guò)程。微粒群算法提供了每個(gè)個(gè)體在這個(gè)過(guò)程中的覓食規(guī)則，使鳥類覓食過(guò)程與整個(gè)粒子群的搜索過(guò)程能夠做到有效的銜接，從而使其有效地應(yīng)用于解決復(fù)雜的優(yōu)化問(wèn)題。

本文介紹了混合離散微粒群算法的具體實(shí)現(xiàn)過(guò)程。該算法采用混合離散微粒群算法對(duì)問(wèn)題解空間進(jìn)行有效快速的全局搜索，為避免對(duì)粒子的搜索陷入局部最優(yōu)，我們引入了一種變異機(jī)制來(lái)改變算法的位置更新公式，使得其全局搜索能夠更快更迅速地獲得較優(yōu)解存在的區(qū)域；進(jìn)而采用插入法和兩點(diǎn)鄰域交換法來(lái)構(gòu)造局部搜索，更加有效地在全局搜索得到的較優(yōu)解鄰域中進(jìn)行更加細(xì)致的搜索，從而使得算法具有更強(qiáng)的搜索能力，為進(jìn)一步獲得優(yōu)質(zhì)解奠定了基礎(chǔ)。

3 算法流程

3.1 解的編碼

解的編碼方式有基于工件的編碼、基于機(jī)器的編碼、基于隨機(jī)鍵的編碼等。在可重入作業(yè)車間調(diào)度問(wèn)題中，最常用的編碼方式則是直接采用工件的排序，故本文算法的編碼規(guī)則采用基于工件的編碼規(guī)則。

3.2 基于混合離散微粒群算法的全局搜索

混合離散微粒群算法的搜索過(guò)程是建立在微粒群算法的基礎(chǔ)上的，在位置更新公式中加入了新的因素，后續(xù)實(shí)驗(yàn)表明該算法更加快速有效。步驟如下：

A、種群初始化：種群規(guī)模為M，采用隨機(jī)方法產(chǎn)生初始化種群，直至初始解的數(shù)量達(dá)到種群規(guī)模的要求；

B、在給定的空間隨機(jī)產(chǎn)生Ps-1個(gè)微粒的離散位置矢量，其中Ps代表群體規(guī)模，確定各微粒對(duì)應(yīng)的加工順序，并進(jìn)行調(diào)度目標(biāo)的評(píng)價(jià)；

C、采用位置更新公式更新所有微粒的位置。

首先聲明，每個(gè)微粒對(duì)應(yīng)著一個(gè)工件加工排序。

從各類文獻(xiàn)的總結(jié)結(jié)果中得出，微粒群優(yōu)化機(jī)制[11]可以這樣理解：已經(jīng)產(chǎn)生的第一代微粒基于自己伙伴的飛行經(jīng)驗(yàn)不斷調(diào)整自己的位置和速度，從而朝著最佳位置飛行，也就是說(shuō)，微粒的新位置是其速度、自身最佳位置和群體最佳位置相互作用的結(jié)果，最終確定最佳位置。根據(jù)以上機(jī)制，我們可以得到如下位置更新公式

上述位置更新公式由三部分依次執(zhí)行構(gòu)成，下面逐一解釋。

第一部分

第二部分

第三部分

為了避免陷入局部最優(yōu)解，提高算法性能和搜索能力，我們?cè)谖⒘５奈恢酶鹿街凶魅缦赂倪M(jìn)：

隨機(jī)選取一個(gè)微粒的最佳位置所對(duì)應(yīng)的最優(yōu)值，與當(dāng)前微粒最優(yōu)值做比較，若當(dāng)前微粒的目標(biāo)值大于隨機(jī)選取的微粒的目標(biāo)值，則選用當(dāng)前微粒，并取代隨機(jī)選取的那個(gè)微粒最優(yōu)位置對(duì)應(yīng)的粒子。根據(jù)更新后的微粒，隨機(jī)生成若干位置，把這些位置對(duì)應(yīng)的值相互交換，得到新的微粒，再對(duì)其進(jìn)行目標(biāo)值的優(yōu)劣比較，選擇優(yōu)者進(jìn)入下一代的搜索。

3.3 局部搜索

對(duì)于車間生產(chǎn)調(diào)度問(wèn)題，這里所提到的兩種有效的局部搜索都是在文獻(xiàn)中經(jīng)常使用的。第一種是將工件排序中位置u與位置v之間的工件進(jìn)行倒序排列(inverse(π,u,v))，第二種是交換工件排序中位置u和位置v處的工件(interchange(π,u,v))，實(shí)驗(yàn)證明，這兩種局部搜索方法皆能夠提高算法性能，幫助算法更快地找到最優(yōu)解存在區(qū)域。因此，我們采用上述倒序操作(inverse)和交換操作(interchange)來(lái)構(gòu)造局部搜索。所構(gòu)造的局部搜索步驟如下：

步驟1：對(duì)于所選定的第i個(gè)個(gè)體的工件排序πi_0；

步驟2：擾動(dòng)階段

隨機(jī)選擇u和v兩個(gè)位置，當(dāng)u≠v時(shí)；πi=interchange(πi_0,u,v)；

步驟3：探索階段

Set loop=1； //設(shè)置循環(huán)體；

Do

隨機(jī)選擇u和v，當(dāng)u≠v時(shí)； //選擇u和v不同位置的工件；

令πi_1=inverse(πi,u,v)； //執(zhí)行inverse操作；

iff(πi_1)

loop++； //繼續(xù)循環(huán)，直到循環(huán)次數(shù)達(dá)到為止；

While loop<(n*(n-1))；

步驟4：如果f(πi)

步驟5：將πi_0重新轉(zhuǎn)換為Xi(t)； //循環(huán)結(jié)束后，選擇最優(yōu)工件排序及調(diào)度目標(biāo)值；

在上述步驟中，步驟2是擾動(dòng)階段，引導(dǎo)算法跳出局部最優(yōu)，使其在不同區(qū)域進(jìn)行探索。步驟3是對(duì)步驟2得到的鄰域進(jìn)行深入開(kāi)發(fā)，得到更優(yōu)解。從而有利于算法更快更有效地搜索存在不同優(yōu)質(zhì)解的區(qū)域，提高了混合離散微粒群算法的搜索與開(kāi)發(fā)能力。

4 仿真試驗(yàn)比較

為了驗(yàn)證混合離散微粒群算法的有效性，我們采用隨機(jī)生成不同規(guī)模的試驗(yàn)例子來(lái)測(cè)試混合離散微粒群算法的性能。有以下規(guī)模組合n*m*l。各個(gè)工件在各個(gè)機(jī)器上的每次重入加工時(shí)間服從[1,100]的均勻分布。最大完成時(shí)間C是整數(shù)。

每個(gè)工件的完成時(shí)間規(guī)定如下：

步驟1：對(duì)每個(gè)不同的問(wèn)題p，隨機(jī)生成工件排序。

步驟2：計(jì)算評(píng)價(jià)步驟1中的工件排序，得到目標(biāo)值。

步驟3：針對(duì)每個(gè)測(cè)試?yán)樱?dú)立運(yùn)行混合離散微粒群算法20次，將得到的結(jié)果進(jìn)行比較研究。

以Delphi 7.0為開(kāi)發(fā)環(huán)境，采用操作系統(tǒng)為Windows 7、CPU在Intel Celeron 2.40 GHz以上、內(nèi)存256 MB以上、硬盤80 GB以上、顯示器SVGA高分辨率彩色的PC。

通過(guò)一個(gè)實(shí)例演示。設(shè)置合理的算法參數(shù)，如算法的運(yùn)行代數(shù)為200(設(shè)置范圍為[5,1000]間整數(shù))，慣性權(quán)重系數(shù)W為0.5(設(shè)置范圍為[0,1]間實(shí)數(shù))，認(rèn)知系數(shù)C1為0.5(設(shè)置范圍為[0,1]間實(shí)數(shù))，社會(huì)系數(shù)C2為0.5(設(shè)置范圍為[0,1]間實(shí)數(shù))，設(shè)置“工件數(shù)”為10(設(shè)置范圍為[1,100]間整數(shù))，“機(jī)器數(shù)”為5(設(shè)置范圍為[1,20]間整數(shù))，“可重入次數(shù)”為3(設(shè)置范圍為[1,10]間整數(shù))。運(yùn)行2種算法，即無(wú)局部搜索的DPSO算法(DPSO_noLS)和帶局部搜索的DPSO算法(DPSO)，可得如圖1所示結(jié)果。

圖1 DPSO_noLS和DPSO運(yùn)行結(jié)果比較Fig.1 Operation results comparison between DPSO_noLS and DPSO

主界面右上半部分的曲線圖形為相應(yīng)算法第1至第200代每代最優(yōu)個(gè)體(即截止當(dāng)前代算法找到的最優(yōu)個(gè)體)對(duì)應(yīng)的適配值(即最大完工時(shí)間makespan)曲線，從曲線可知兩種算法均能不斷改進(jìn)搜索質(zhì)量，但DPSO算法對(duì)應(yīng)的曲線下降更快，這驗(yàn)證了加入局部搜索是可行且有效的。主界面左上部分的兩個(gè)文本框中分別顯示兩種算法運(yùn)行200代中每代對(duì)應(yīng)的最優(yōu)值(即截止當(dāng)前代算法得到的最小makespan)，從中可知DPSO算法得到的每代最優(yōu)值相對(duì)較小，只是由于加入了局部搜索，使得算法運(yùn)行時(shí)間較長(zhǎng)。主界面下半部分的文本框中顯示了算法第1代和第200代的運(yùn)行結(jié)果，包括第1代和第200代對(duì)應(yīng)的最優(yōu)值和工件排列。

5 結(jié)論

本文提出混合離散微粒群算法DPSO，用于求解可重入作業(yè)車間調(diào)度問(wèn)題。混合離散微粒群算法是學(xué)術(shù)界首個(gè)基于離散微粒群算法求解該問(wèn)題的算法，有著巨大的影響力。混合離散微粒群算法利用改進(jìn)的位置更新公式對(duì)問(wèn)題解空間進(jìn)行有效快速的全局搜索，并迅速準(zhǔn)確地發(fā)現(xiàn)存在優(yōu)質(zhì)解的區(qū)域，同時(shí)采用基于倒序操作和交換操作的兩種有效的局部搜索來(lái)針對(duì)存在優(yōu)質(zhì)解的區(qū)域進(jìn)行深入搜索，提高了算法性能，在有限的時(shí)間內(nèi)，加強(qiáng)了算法的搜索能力，提高了算法效率。

[1]PARPINELLI R S, LOPES H S. New inspirations in swarm intelligence:A survey[J] International Journal of Bio-Inspired Computation，2011，3(1):146-159.

[2]馬丁,陳慶新,毛寧，等.具有交貨期約束帶準(zhǔn)備時(shí)間的平行機(jī)分批調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2012，18(01):159-188.

[3]WANG L, WANG S Y, XU Y,et al. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J] . Computers & Industrial Engineering，2012，62(4): 917-926.

[4]汪慎文,丁立新,張文生.差分進(jìn)化算法研究進(jìn)展[J]. 武漢大學(xué)學(xué)報(bào)(理學(xué)版)，2014，60(4): 283-292.

[5]YANG X S. Flower pollination algorithm for global optimization[C]//International Conference on Unconventional Computing and Natural Computation. Berlin Springer，2012: 240-249..

[6]李修琳,魯建廈,柴國(guó)鐘,等.混合蜂群算法求解柔性作業(yè)車間調(diào)度問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17(7): 1495-1500.

[7]吳尤可,王田.基于蟻群群體智能理論的創(chuàng)新政策擴(kuò)散研究[J]. 科學(xué)學(xué)與科學(xué)技術(shù)管理，2014，35(4): 35-40.

[8]ZHANG R, SONG S J, WU C. A hybrid artificial bee colony algorithm for the job shop scheduling problem[J] .International Journal of Production Economics，2013，141 (1) : 167-178.

[9]WANG L, ZHOU G, XU Y, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J] .The International Journal of Advanced Manufacturing Technology，2012,60(1): 303-315.

[10]王圣堯,王凌,許燁.求解混合流水車間調(diào)度問(wèn)題的分布估計(jì)算法[J]. 自動(dòng)化學(xué)報(bào)，2012，38(3): 437-433.

[11]夏小翔.改進(jìn)的微粒群優(yōu)化算法[J].鄂州大學(xué)學(xué)報(bào)，2011，18(5): 5-7.

Improveddiscreteparticleswarmoptimizationalgorithmtosolvethereentrantjob-shopschedulingproblem

WANJing

(ShandongTechnologicalCenterofOceanographicInstrumentation，InstituteofOceanographicInstrumentation,ShandongAcademyofSciences，Qingdao26600,China)

∶In this paper, by combining the existing discrete particle swarm optimization algorithm with a small but effective local search, an effective hybrid discrete particle swarm optimization algorithm was formed. This paper also discussed how to fuse the local search to optimize the discrete particle swarm. And the effectiveness of the proposed algorithm has been proved by the comparison of the simulation results.

∶discrete particle swarm optimization algorithm；local search；job-shop

10.3976/j.issn.1002-4026.2017.06.017

2017-01-03

青島市市南區(qū)科技發(fā)展基金(2016-2-012-ZH )

萬(wàn)婧(1989—)，女，助理工程師，研究方向?yàn)楹Ｑ蠹夹g(shù)。E-mail:1066358426@qq.com

TP301.6

A

1002-4026(2017)06-105-05