Abstract：For Flexible Job-shop Scheduling Problem (FJSP) with non-deterministic polynomial characteristics, a cooperative hybrid imperialist competitive algorithm was proposed to minimize the maximum makespan. Firstly, based on process characteristics of standard Imperialist Competitive Algorithm (ICA), improvement of adaptive parameters was designed to improve the convergence speed of the algorithm. Secondly, the reform of the empire and the colonies was introduced. Aiming to the stages of process arrangement and machine selection, a multi-mutation reform strategy was proposed to improve the local search efficiency of the algorithm. Finally, the mechanism for exchanges and cooperation among countries in the mainland was created to promote the exchange of information among outstanding countries and improve the global search capability of the algorithm. By testing on many flexible shop scheduling examples, the experimental results show that the proposed algorithm outperforms many swarm intelligence algorithms in terms of quality and stability, and it is more suitable for solving this kind of scheduling problems.
[1] BRUCKER P, SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4):369-375. [2] GAO L, PAN Q-K. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem[J]. Information Sciences, 2016, 372:655-676. [3] ZUO Y, GONG M G, JIAO L C. Adaptive multimeme algorithm for flexible job shop scheduling problem[J].Natural Computing, 2017, 16(4):677-698. [4] SREEKARA REDDY M B S, RATNAM C H, AGRAWAL R, et al. Investigation of reconfiguration effect on makespan with social network method for flexible job shop scheduling problem[J]. Computers and Industrial Engineering, 2017, 110:231-241. [5] 张洁,张朋.基于两阶段蚁群算法的带非等效并行机的作业车间调度[J].机械工程学报,2013,49(6):136-144.(ZHANG J, ZHANG P. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines[J]. Journal of Mechanical Engineering, 2013, 49(6):136-144.) [6] ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm:an algorithm for optimization inspired by imperialistic competition[C]//CEC'07:Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2007:4661-4667. [7] 杨小东,康雁,柳青.求解作业车间调度问题的混合帝国主义竞争算法[J].计算机应用,2017,37(2):517-522.(YANG X D, KANG Y, LIU Q. Hybrid imperialist competitive algorithm for solving job-shop scheduling problem[J]. Journal of Computer Applications, 2017, 37(2):517-522.) [8] 方晨,王凌.资源约束项目调度研究综述[J].控制与决策,2010,25(5):641-650.(FANG C, WANG L. Survey on resource-constrained project scheduling[J].Control and Decision, 2010, 25(5):641-650.) [9] 桂忠艳,杨静,谢志强.基于剪枝分层的柔性加工车间调度算法[J].控制与决策,2017,32(11):1921-1932.(GUI Z Y, YANG J, XIE Z Q. Scheduling algorithm for flexible job shop based on pruning and layering[J]. Control and Decision, 2017, 32(11):1921-1932.) [10] 王芳,唐秋华,饶运清.求解柔性流水车间调度问题的高效分布估算算法[J].自动化学报,2017,43(2):280-293.(WANG F, TANG Q H, RAO Y Q. Efficient estimation of distribution for flexible hybrid flow shop scheduling[J]. Acta Automatica Sinica, 2017, 43(2):280-293.) [11] 郭婉青,叶东毅.帝国竞争算法的进化优化[J].计算机科学与探索,2014,8(4):473-482.(QUO W Q, YE D Y. Evolutionary optimization of imperialist competitive algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(4):473-482.) [12] 张鑫龙,陈秀万,肖汉,等.一种求解旅行商问题的新型帝国竞争算法[J].控制与决策,2016,31(4):586-592.(ZHANG X L, CHEN X W, XIAO H, et al. A new imperialist competitive algorithm for solving TSP problem[J]. Control and Decision, 2016, 31(4):586-592.) [13] 谢涛,董滔.基于混合GA算法的工作流作业调度队列优化[J].计算机工程与应用,2016,52(24):85-90.(XIE T, DONG T. Optimization of workflow scheduling queue based on hybrid genetic algorithm[J]. Computer Engineering and Applications, 2016, 52(24):85-90.) [14] 吴伟民,陈宝财,陈丹.基于双种群的进化策略算法[J].计算机应用,2009,29(5):1254-1256.(WU W M, CHEN B C, CHEN D. Evolutionary strategy algorithm based on two sub-groups[J]. Journal of Computer Applications, 2009, 29(5):1254-1256.) [15] 程子安,童鹰.双种群混合遗传算法求解柔性作业车间调度问题[J].计算机工程与设计,2016,37(6):1636-1642.(CHEN Z A, TONG Y. Double population hybrid genetic algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Design, 2016, 37(6):1636-1642.) [16] 王万良,赵澄,熊婧,等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报,2008,20(16):4326-4329.(WANG W L, ZHAO C, XIONG J, et al. Method to resolve flexible job-shop scheduling problem based on improved ant colony algorithm[J]. Journal of System Simulation, 2008, 20(16):4326-4329.) [17] 张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124.(ZHANG C Y, RAO Y Q, LI P G, et al. Bilevel genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2007, 43(4):119-124.) [18] 张静,王万良,徐新黎.基于改进粒子群算法求解柔性作业车间批量调度问题[J].控制与决策,2012,27(4):513-518.(ZHANG J, WANG W L, XU X L. Improved particle swarm algorithm for batch splitting flexible job shop scheduling[J].Control and Decision, 2012, 27(4):513-518.) [19] 曾强,杨育,王小磊,等.基于多规则设备分配及工序排序的FJSP多目标集成优化方法[J].计算机集成制造统,2011,17(5):980-989.(ZENG Q, YANG Y, WANG X L, et al. Integrated multi-objective optimization method for FJSP based on multiple rule machine assignment and job sequencing[J]. Computer Integrated Manufacturing Systems, 2011, 17(5):980-989.) [20] 戴月明,王明慧,王春.骨干双粒子群算法求解柔性作业车间调度问题[J].系统仿真学报,2017,29(6):1268-1276.(DAI Y M, WANG M H, WANG C. Double bare bones particle swarm algorithm for solving flexible job-shop scheduling problem[J]. Journal of System Simulation, 2017, 29(6):1268-1276.) [21] 孔飞,吴定会,纪志成.基于双层粒子群优化算法的柔性作业车间调度优化[J].计算机应用,2015,35(2):476-480.(KONG F, WU D H, JI Z C. Flexible job-shop scheduling optimization based on two-layer particle swarm optimization algorithm[J]. Journal of Computer Applications, 2015, 35(2):476-480.) [22] 周恺,纪志成.关于柔性作业车间调度问题的仿真研究[J].计算机仿真,2016,33(3):282-287.(ZHOU K, JI Z C. Simulation and research of flexible job shop scheduling problem[J]. Computer Simulation, 2016, 33(3):282-287.) LYU Cong, born in 1993, M. S. candidate. His research interests include intelligent job-shop scheduling, intelligent algorithm optimization.WEI Kanglin, born in 1975, Ph. D., associate professor. His research interests include artificial intelligence control, intelligent detection equipment.
2018, Vol. 38 
