CIESC Journal ›› 2017, Vol. 68 ›› Issue (3): 1073-1080.DOI: 10.11949/j.issn.0438-1157.20161625

Previous Articles     Next Articles

Improved GA and global random machine selection based on key operation to solve FJSP

XU Wenxing1, WANG Qin1,2, BIAN Weibin1,2, WANG Wanhong1,2, DONG Yiqun1   

  1. 1 College of Information Engineering, Beijing Institute of Petrochemical Technology, Beijing 102617, China;
    2 College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China
  • Received:2016-11-16 Revised:2016-11-26 Online:2017-03-05 Published:2017-03-05
  • Contact: 10.11949/j.issn.0438-1157.20161625
  • Supported by:

    supported by the National Natural Science Foundation of China (61304217) and the Scientific Research Common Program of Beijing Municipal Commission of Education (KM201510017003).

基于关键工序的全局随机机器选择和改进GA求解FJSP

徐文星1, 王琴1,2, 边卫斌1,2, 王万红1,2, 董轶群1   

  1. 1 北京石油化工学院信息工程学院, 北京 102617;
    2 北京化工大学信息科学与技术学院, 北京 100029
  • 通讯作者: 董轶群,dongyq@bipt.edu.cn
  • 基金资助:

    国家自然科学基金项目(61304217);北京市教育委员会科技计划项目(KM201510017003)。

Abstract:

In order to improve the diversity of initial population and consider the operation sequence constraints of the same artifact at the same time, the stack was used to storage all operations in the view of the FJSP machine selection problem, in which the makespan was the optimization objective. Global random initialization method based on the key operation was proposed to solve the machine selection problem of FJSP, in which the key operation containing the only optional machine can directly affect the total load machine and processing time. To avoid the basic genetic algorithm trapped in local optimum when solving FJSP, re-activation mechanism was added to the GA algorithm, by which the diversity of population can be increased. Finally, in the view of the FJSP benchmark examples, the effectiveness of the GRS initialization mechanism and the reliability of the proposed improved algorithm were verified respectively by analyzing the performance comparison of the initial machine selection parts and the experimental results of solving FJSP by the genetic algorithm with different initializations.

Key words: flexible job-shop scheduling, optimization, species diversity, machine selection, GRS initialization mechanism, re-activation mechanism, genetic algorithm, numerical analysis

摘要:

以FJSP的最大完工时间作为优化目标,在考虑同一工件的工序顺序约束的同时,为提高初始种群的多样性,针对FJSP的机器选择问题采用堆栈方式存储工序。P-FJSP中只有一台机器可选的关键工序能直接影响机器总负荷和工件加工时间,进而提出了一种基于关键工序的全局随机选择(GRS)初始化方法。为了避免基本遗传算法在求解FJSP时陷入局部极优而停滞,在GA算法中加入再激活(re-activation)机制,旨在重新激活种群,增加种群的多样性。最后,针对FJSP基准测试算例进行数值分析,通过初始机器选择部分的性能对比实验、不同初始方式下遗传算法求解FJSP对比实验分别验证了GRS初始化机制的有效性和所提改进算法的可靠性。

关键词: 柔性作业车间调度, 优化, 种群多样性, 机器选择, GRS初始化机制, 再激活机制, 遗传算法, 数值分析

CLC Number: