萬婧

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

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

萬婧

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

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

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

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

1 問題模型

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

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表示機器數(shù)，R表示n個工件中每個工件的重入次數(shù)，n表示工件數(shù)，π=[π1,π2,…,πR]是工件加工排序，πj∈{1,…,n}(j=1,…,R)表示排序π中第j個位置的工件，l(πj)表示工件πj在[π1,…,πj]中重復出現(xiàn)的次數(shù)，p(πj,k,l(πj)是工件πj第l(πj)次進入第k臺機器的加工時間，C(πj,k,l(πj))是工件πj第l(πj)次進入第k臺機器的完工時間，C(π0,k,l(π0))=0，C(πj,k,0)=0，k∈{1,…,m}，優(yōu)化目標是找到一個最優(yōu)排序π*，使得對應的最早完工時間Cmax最小。

2 研究方法

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

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

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

3 算法流程

3.1 解的編碼

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

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

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

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

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

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

首先聲明，每個微粒對應著一個工件加工排序。

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

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

第一部分

第二部分

第三部分

為了避免陷入局部最優(yōu)解，提高算法性能和搜索能力，我們在微粒的位置更新公式中作如下改進：

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

3.3 局部搜索

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

步驟1：對于所選定的第i個個體的工件排序πi_0；

步驟2：擾動階段

隨機選擇u和v兩個位置，當u≠v時；πi=interchange(πi_0,u,v)；

步驟3：探索階段

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

Do

隨機選擇u和v，當u≠v時； //選擇u和v不同位置的工件；

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

iff(πi_1)

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

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

步驟4：如果f(πi)

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

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

4 仿真試驗比較

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

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

步驟1：對每個不同的問題p，隨機生成工件排序。

步驟2：計算評價步驟1中的工件排序，得到目標值。

步驟3：針對每個測試例子，獨立運行混合離散微粒群算法20次，將得到的結(jié)果進行比較研究。

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

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

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

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

5 結(jié)論

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

[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]馬丁,陳慶新,毛寧，等.具有交貨期約束帶準備時間的平行機分批調(diào)度[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]. 武漢大學學報(理學版)，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]李修琳,魯建廈,柴國鐘,等.混合蜂群算法求解柔性作業(yè)車間調(diào)度問題[J].計算機集成制造系統(tǒng)，2011，17(7): 1495-1500.

[7]吳尤可,王田.基于蟻群群體智能理論的創(chuàng)新政策擴散研究[J]. 科學學與科學技術(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)度問題的分布估計算法[J]. 自動化學報，2012，38(3): 437-433.

[11]夏小翔.改進的微粒群優(yōu)化算法[J].鄂州大學學報，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 )

萬婧(1989—)，女，助理工程師，研究方向為海洋技術(shù)。E-mail:1066358426@qq.com

TP301.6

A

1002-4026(2017)06-105-05