柔性作業(yè)車(chē)間調(diào)度的分布式粒子群優(yōu)化算法

劉勝輝+任娟+張淑麗

摘 要：針對(duì)柔性作業(yè)車(chē)間調(diào)度問(wèn)題的特性，提出了一種分布式粒子群優(yōu)化算法以求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題，該算法以最小化最大完工時(shí)間為目標(biāo)，為解決傳統(tǒng)粒子群算法在遇到突發(fā)事件時(shí)不能實(shí)時(shí)進(jìn)行響應(yīng)做出合理決策的問(wèn)題，在算法中設(shè)計(jì)了兩個(gè)多Agent粒子群優(yōu)化模型。最后，使用經(jīng)典算例對(duì)算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)表明多Agent粒子群優(yōu)化模型具有合理性，該算法能夠有效解決柔性作業(yè)車(chē)間調(diào)度問(wèn)題。

關(guān)鍵詞：關(guān)鍵詞：柔性作業(yè)車(chē)間調(diào)度；粒子群優(yōu)化；分布式；多Agent系統(tǒng)

DOI：10.15938/j.jhust.2017.03.001

中圖分類號(hào)： TP301

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2017）03-0001-07

Abstract：According to the characteristics of the Flexible job shop scheduling problem， the minimum makespan as measures， we proposed a distributed particle swarm optimization algorithm aiming to solve flexible job shop scheduling problem. The algorithm adopts the method of distributed ideas to solve problems and we are established for two multiagent particle swarm optimization model in this algorithm， it can solve the traditional particle swarm optimization algorithm when making decisions in real time according to the emergencies. Finally， some benthmark problems were experimented and the results are compared with the traditional algorithm. Experimental results proved that the developed distributed PSO is enough effective and efficient to solve the FJSP and it also verified the reasonableness of the multiagent particle swarm optimization model.

Keywords：flexible job shop scheduling； particle swarm optimization； distributed； multiagent system； maximum completion time

表中傳統(tǒng)PSO的CPU運(yùn)行時(shí)間引用文[13]。從表3可以看出，由于分布式粒子群優(yōu)化算法在多Agent系統(tǒng)上運(yùn)行，因此算法速度更加快速。

MAPSO2模型，執(zhí)行Agent同步所有動(dòng)作的等待時(shí)間也包括，所以整個(gè)加工時(shí)間比集中式PSO要長(zhǎng)。而MAPSO2模型的突出特點(diǎn)是，能夠在有限的內(nèi)存和資源條件下在多個(gè)嵌入式系統(tǒng)中實(shí)現(xiàn)PSO。另外，MAPSO2模型的優(yōu)勢(shì)是Agent都集成在優(yōu)化階段。為了使系統(tǒng)最大限度地收斂于最佳粒子，遷移策略也是常用的方法，用來(lái)指導(dǎo)探究搜索空間的新領(lǐng)域。

5 結(jié) 語(yǔ)

隨著工業(yè)和制造系統(tǒng)的發(fā)展，要求對(duì)生產(chǎn)過(guò)程中出現(xiàn)的諸如機(jī)器故障、機(jī)器維護(hù)、連接中斷等突發(fā)事件及時(shí)作出處理，這就需要對(duì)柔性作業(yè)車(chē)間調(diào)度問(wèn)題進(jìn)行進(jìn)一步研究，以響應(yīng)突發(fā)事件。本文提出的分布式粒子群優(yōu)化算法，結(jié)合多Agent系統(tǒng)，對(duì)問(wèn)題分散決策，使每個(gè)實(shí)體都參與問(wèn)題的解決。提出兩個(gè)基于多Agent系統(tǒng)的分布式PSO模型，MAPSO架構(gòu)可以根據(jù)資源意外或突發(fā)情況對(duì)系統(tǒng)進(jìn)行重新配置。用算例進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明該分布式粒子群優(yōu)化算法具有可行性和有效性，該算法對(duì)生產(chǎn)實(shí)踐具有一定的指導(dǎo)作用未來(lái)的研究方向是開(kāi)發(fā)一個(gè)嵌入式MAPSO，將問(wèn)題分布到多個(gè)嵌入式系統(tǒng)中，使每個(gè)實(shí)體都參與進(jìn)來(lái)，而且要更好地控制能源損耗。

參 考 文 獻(xiàn)：

[1] 劉勝輝， 張淑麗， 滕春賢. 考慮不確定因素的單件小批作業(yè)計(jì)劃與調(diào)度動(dòng)態(tài)算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2011， 32（4）： 471-475.

[2] 彭建剛， 劉明周， 張銘鑫， 等. 多目標(biāo)柔性作業(yè)車(chē)間調(diào)度算法研究綜述[J]. 中國(guó)機(jī)械工程， 2014， 25（23）： 3244-3254.

[3] 汪俊亮， 張潔， 秦威， 等. 加工時(shí)間不確定的柔性作業(yè)車(chē)間魯棒調(diào)度方法[J]. 中國(guó)機(jī)械工程， 2015， 26（5）： 627-631.

[4] 胥小波， 鄭康鋒， 李丹， 等. 新的混沌粒子群優(yōu)化算法[J]. 通信學(xué)報(bào)， 2012， 33（1）： 24-31.

[5] 周飛紅， 廖子貞. 自適應(yīng)慣性權(quán)重的分組并行粒子群優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2014， 50（8）： 40-44.

[6] 王亞， 熊焰， 龔旭東， 等. 基于混沌 PSO 算法優(yōu)化 RBF 網(wǎng)絡(luò)入侵檢測(cè)模型[J]. 計(jì)算機(jī)工程與應(yīng)用， 2013， 49（10）： 84-87.

[7] 賈兆紅， 朱建建， 陳華平. 柔性作業(yè)車(chē)間調(diào)度的動(dòng)態(tài)禁忌粒子群優(yōu)化算法[J]. 華南理工大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2012， 40（1）： 69-75.

[8] MOTAGHEDILARIJANI A， SABRILAGHAIE K， HEYDARI M. Solving Flexible Job Shop Scheduling With Multi Objective Approach[J]. International Journal of Industrial Engineering and Production Research， 2010， 21（4）： 197-209.

[9] GIRISH B， JAWAHAR N. A Particle Swarm Optimization Algorithm for Flexible Job Shop Scheduling Problem[J]. IEEE conference on Automation Science and Engineering， 2009， 16（1）： 298-303.

[10]陸曈曈， 鄭小東， 張屹， 等. 改進(jìn)元胞遺傳算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J]. 現(xiàn)代制造工程， 2015（9）： 42-47.

[11]ZHANG G， SHAO X， LI P， GAO L. An Effective Hybrid Particle Swarm Optimization Algorithm for Multiobjective Flexible Jobshop Scheduling Problem[J]. Computers and Industrial Engineering， 2009， 56（1）： 1309-1318.

[12]TRELEA I. The Particle Swarm Optimization Algorithm： Convergence Analysis and Parameter Selection[J]. Information Processing Letters， 2003（85）： 317-325.

[13]KACEM L， HAMMADI S， BORNE P. Approach by Localization and Multi Objective Evolutionary Optimization for Flexible Jobshop Scheduling Problems[J]. IEEE Transaction Systems， Man， and Cybernetics， 2002， 32（1）： 1-13.

[14]NOUIRI M， JEMAI A， BEKRAR A， NIAR S， AMMARI A C. An Effective Particle Swarm Optimization to Solve Flexible Job Shop scheduling Problem[C]// In Presented at the 5th IESM conference， 2013.

[15]HENCHIRI A， ENNGIROU M. Particle Swarm Optimization Combined with Tabu Search in a Multiagent Model for Flexible Job Shop Problem[J]. Computer Science， 2013， 7929： 385-394.

（編輯：溫澤宇）