柔性作業車間調度的分布式粒子群優化算法

劉勝輝+任娟+張淑麗

摘 要：針對柔性作業車間調度問題的特性，提出了一種分布式粒子群優化算法以求解柔性作業車間調度問題，該算法以最小化最大完工時間為目標，為解決傳統粒子群算法在遇到突發事件時不能實時進行響應做出合理決策的問題，在算法中設計了兩個多Agent粒子群優化模型。最后，使用經典算例對算法進行了驗證，實驗表明多Agent粒子群優化模型具有合理性，該算法能夠有效解決柔性作業車間調度問題。

關鍵詞：關鍵詞：柔性作業車間調度；粒子群優化；分布式；多Agent系統

DOI：10.15938/j.jhust.2017.03.001

中圖分類號： TP301

文獻標志碼： A

文章編號： 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

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

MAPSO2模型，執行Agent同步所有動作的等待時間也包括，所以整個加工時間比集中式PSO要長。而MAPSO2模型的突出特點是，能夠在有限的內存和資源條件下在多個嵌入式系統中實現PSO。另外，MAPSO2模型的優勢是Agent都集成在優化階段。為了使系統最大限度地收斂于最佳粒子，遷移策略也是常用的方法，用來指導探究搜索空間的新領域。

5 結 語

隨著工業和制造系統的發展，要求對生產過程中出現的諸如機器故障、機器維護、連接中斷等突發事件及時作出處理，這就需要對柔性作業車間調度問題進行進一步研究，以響應突發事件。本文提出的分布式粒子群優化算法，結合多Agent系統，對問題分散決策，使每個實體都參與問題的解決。提出兩個基于多Agent系統的分布式PSO模型，MAPSO架構可以根據資源意外或突發情況對系統進行重新配置。用算例進行了測試，實驗結果表明該分布式粒子群優化算法具有可行性和有效性，該算法對生產實踐具有一定的指導作用未來的研究方向是開發一個嵌入式MAPSO，將問題分布到多個嵌入式系統中，使每個實體都參與進來，而且要更好地控制能源損耗。

參 考 文 獻：

[1] 劉勝輝， 張淑麗， 滕春賢. 考慮不確定因素的單件小批作業計劃與調度動態算法[J]. 哈爾濱工程大學學報， 2011， 32（4）： 471-475.

[2] 彭建剛， 劉明周， 張銘鑫， 等. 多目標柔性作業車間調度算法研究綜述[J]. 中國機械工程， 2014， 25（23）： 3244-3254.

[3] 汪俊亮， 張潔， 秦威， 等. 加工時間不確定的柔性作業車間魯棒調度方法[J]. 中國機械工程， 2015， 26（5）： 627-631.

[4] 胥小波， 鄭康鋒， 李丹， 等. 新的混沌粒子群優化算法[J]. 通信學報， 2012， 33（1）： 24-31.

[5] 周飛紅， 廖子貞. 自適應慣性權重的分組并行粒子群優化算法[J]. 計算機工程與應用， 2014， 50（8）： 40-44.

[6] 王亞， 熊焰， 龔旭東， 等. 基于混沌 PSO 算法優化 RBF 網絡入侵檢測模型[J]. 計算機工程與應用， 2013， 49（10）： 84-87.

[7] 賈兆紅， 朱建建， 陳華平. 柔性作業車間調度的動態禁忌粒子群優化算法[J]. 華南理工大學學報： 自然科學版， 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]. 現代制造工程， 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.

（編輯：溫澤宇）