Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 1882-1887.DOI: 10.11772/j.issn.1001-9081.2017122933

Previous Articles     Next Articles

Cooperative hybrid imperialist competitive algorithm for flexible job-shop scheduling problem

LYU Cong, WEI Kanglin   

  1. College of Electrical Engineering and New Energy, China Three Gorges University, Yichang Hubei 443002, China
  • Received:2017-12-15 Revised:2018-02-14 Online:2018-07-10 Published:2018-07-12

柔性车间调度问题的协作混合帝国算法

吕聪, 魏康林   

  1. 三峡大学 电气与新能源学院, 湖北 宜昌 443002
  • 通讯作者: 魏康林
  • 作者简介:吕聪(1993-),男,山东莱芜人,硕士研究生,主要研究方向:智能车间调度、智能算法寻优;魏康林(1975-),男,四川成都人,副教授,博士,主要研究方向:人工智能控制、智能检测设备。

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.

Key words: Flexible Job-shop Scheduling Problem (FJSP), Imperialist Competitive Algorithm (ICA), adaptive parameter, multi-variation reform, cooperation mechanism

摘要: 针对柔性车间调度问题(FJSP)的非确定性多项式特性,提出一种新的改进算法——协作混合帝国算法,用于寻找最小化最大完工时间的调度。首先,根据标准帝国竞争算法(ICA)的流程特性,设计了自适应参数的改进,可提高算法的收敛速度;然后,引入帝国和殖民地双改革变异,并针对工序排序和选择机器的不同阶段提出多变异改革策略,可提高算法的局部搜索效率;最后,创建大陆间国家交流合作机制,促进优秀国家对外信息交流,可提高算法全局搜索能力。通过对多个柔性车间调度实例进行仿真,结果表明,所提出算法在求解质量和稳定性上均优于多种群体智能进化算法,更适合解决该类调度问题。

关键词: 柔性车间调度问题, 帝国竞争算法, 自适应参数, 多变异改革, 公约协作

CLC Number: