• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2019, Vol. 55 ›› Issue (6): 223-232.doi: 10.3901/JME.2019.06.223

• 交叉与前沿 • 上一篇    

基于自适应变级遗传杂草算法的FJSP研究

石小秋, 李炎炎, 邓丁山, 龙伟   

  1. 四川大学制造科学与工程学院 成都 610000
  • 收稿日期:2018-03-22 修回日期:2018-09-12 出版日期:2019-03-20 发布日期:2019-03-20
  • 通讯作者: 李炎炎(通信作者),女,1979年出生,博士,讲师。主要研究方向为物流信息工程、车辆/交通智能技术。E-mail:lyy_scu@163.com
  • 作者简介:石小秋,男,1986年出生,博士研究生。主要研究方向为智能优化算法,供应链网络鲁棒性等。E-mail:315929207@qq.com;邓丁山,男,1992年出生,博士研究生。主要研究方向为智能算法;龙伟,男,1956年出生,博士,博士生导师。主要研究方向为数字化设计与制造技术、交通车辆智能技术、研究机械装备安全评估及可靠性分析、现代制造物流及其规划调度。
  • 基金资助:
    国家自然科学基金(51875371)和国家工信部([2017]327)资助项目。

Self-adaptive Multistage GA-IWO for Solving Flexible Job Shop Scheduling Problem

SHI Xiaoqiu, LI Yanyan, DENG Dingshan, LONG Wei   

  1. School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610000
  • Received:2018-03-22 Revised:2018-09-12 Online:2019-03-20 Published:2019-03-20

摘要: 针对以最小化最大完工时间为目标的柔性作业车间调度问题,建立其数学模型并提出一种自适应变级遗传杂草算法求解之。改进基本入侵杂草优化算法以适应柔性作业车间调度问题的组合优化特点,提出基于总个体数的评价指标,用其分析入侵杂草优化算法在解决柔性作业车间调度问题时的性能及参数对算法的影响,得出入侵杂草优化算法的种群数和个体产生种子数对算法性能的影响关系。分析入侵杂草优化算法和遗传算法在求解柔性作业车间调度问题时各自的优缺点。结合这两种算法,引入汉明距离来测度种群多样性并用该测度值作为变级控制的依据,提出一种根据多样性测度值的动态变化而自适应地在遗传算法和入侵杂草优化算法间串行变级的遗传杂草算法。通过实例对比入侵杂草优化算法、遗传算法和自适应变级遗传杂草算法,证明了自适应变级遗传杂草算法的有效性和优越性。将自适应变级遗传杂草算法用于标准测试实例与多种算法比较,证明了该算法能够有效求解柔性作业车间调度问题。

关键词: 柔性作业车间调度, 遗传算法, 杂草优化算法, 种群多样性, 自适应变级

Abstract: For flexible job shop scheduling problem with minimizing makespan, a mathematical model and a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm are proposed. For the characteristics of flexible job shop scheduling problem, invasive weed optimization is improved. Using some new evaluating indicators based on total number of individuals to evaluate the performance of improved invasive weed optimization, how the population size and weed size affect invasive weed optimization is addressed. Using the new evaluating indicators to evaluate improved invasive weed optimization and genetic algorithm, some differences between them are illustrated. Using hamming distance to measure the population diversity, the value of population diversity is used to control the self-adaptive multistage between invasive weed optimization and genetic algorithm, obtaining a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm. Using some instances to test genetic algorithm, invasive weed optimization, and self-adaptive multistage genetic algorithm/invasive weed optimization, the advantages of self-adaptive multistage genetic algorithm/invasive weed optimization are shown. Using some standard instances to compare a self-adaptive multistage genetic algorithm/invasive weed optimization with other algorithms, the simulation results show that the proposed algorithm can solve flexible job shop scheduling problem effectively.

Key words: flexible job shop scheduling problem, genetic algorithm, invasive weed optimization, population diversity, self-adaptive multistage

中图分类号: