柔性作业车间调度的分布式粒子群优化算法

刘胜辉+任娟+张淑丽

摘 要：针对柔性作业车间调度问题的特性，提出了一种分布式粒子群优化算法以求解柔性作业车间调度问题，该算法以最小化最大完工时间为目标，为解决传统粒子群算法在遇到突发事件时不能实时进行响应做出合理决策的问题，在算法中设计了两个多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.

（編辑：温泽宇）