Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (8): 2242-2248.DOI: 10.11772/j.issn.1001-9081.2020101664

Special Issue: 先进计算

• Advanced computing • Previous Articles     Next Articles

Machine breakdown rescheduling of flexible job shop based on improved imperialist competitive algorithm

ZHANG Guohui, LU Xixi, HU Yifan, SUN Jinghe   

  1. College of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou Henan 450015, China
  • Received:2020-10-27 Revised:2021-01-26 Online:2021-08-10 Published:2021-02-05
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (U1904167, 71871204, 51905494), the Humanities and Social Sciences Planning Fund of Ministry of Education (18YJAZH125), the Supporting Project of the Innovative Research Team in Colleges and Universities of Henan Province (21IRTSTHN018).


张国辉, 陆熙熙, 胡一凡, 孙靖贺   

  1. 郑州航空工业管理学院 管理工程学院, 郑州 450015
  • 通讯作者: 张国辉
  • 作者简介:张国辉(1980-),男,河南新乡人,教授,博士,主要研究方向:智能调度;陆熙熙(1998-),女,河南商丘人,硕士研究生,主要研究方向:智能调度;胡一凡(1997-),男,河南驻马店人,硕士研究生,主要研究方向:智能优化算法、车间调度;孙靖贺(1995-),男,河南沈丘人,硕士研究生,主要研究方向:智能调度、智能优化算法。
  • 基金资助:

Abstract: For the flexible job shop rescheduling problem with machine breakdown, an improved Imperialist Competition Algorithm (ICA) was proposed. Firstly, a flexible job shop dynamic rescheduling model was established with the maximum completion time, machine energy consumption and total delay time as the objective functions, and linear weighting method was applied to three objectives. Then, the improved ICA was proposed to retain the excellent information for the next generation. A roulette selection mechanism was added after the assimilation and revolutionary steps of the general ICA, so that the excellent genes in the initial empire were able to be retained, and the updated empire quality was better and closer to the optimal solution. Finally, after the machine breakdown, the event-driven rescheduling strategy was adopted to reschedule the unprocessed job procedures after the breakdown point. Through production examples, simulation experiments were carried out on three hypothetical machine breakdown scenarios, and the proposed algorithm was compared with improved Genetic Algorithm (GA) and Genetic and Simulated Annealing Algorithm (GASA). Experimental results show that the proposed improved ICA is effective and feasible.

Key words: Imperialist Competitive Algorithm (ICA), Flexible Job-Shop Scheduling Problem (FJSP), dynamic scheduling, machine breakdown, roulette

摘要: 针对机器故障下的柔性作业车间重调度问题,提出了一种改进的帝国竞争算法(ICA)。首先,以最大完工时间、机器能耗和总延迟时间为目标函数建立柔性作业车间动态重调度模型,并对三个目标采用线性加权法;然后提出了改进的ICA来把优良的信息保留到下一代,即在传统ICA的同化和革命步骤后加入一个轮盘赌的选择机制,使初始帝国中的优秀基因得以保留,并且更新后的帝国质量更优,更加贴近最优解;最后,在机器发生故障后,采用事件驱动的重调度策略对故障点后未加工的工序进行重新调度。通过生产实例,对假设的三种机器故障情景进行仿真实验,并把所提算法与改进遗传算法(GA)和遗传算法与模拟退火混合算法(GASA)这两种算法进行比较。实验结果表明了提出的改进ICA是有效且可行的。

关键词: 帝国竞争算法, 柔性作业车间调度问题, 动态调度, 机器故障, 轮盘赌

CLC Number: