计算机与现代化 ›› 2022, Vol. 0 ›› Issue (08): 78-85.

• 计算机仿真 • 上一篇    下一篇

一种改进的求解柔性作业车间调度问题的灰狼算法

  

  1. (延安大学数学与计算机科学学院,陕西延安716000)
  • 出版日期:2022-08-22 发布日期:2022-08-22
  • 作者简介:田云娜(1981—),女,陕西延安人,副教授,博士,研究方向:最优化方法、理论与应用,E-mail: ydtianyunna@163.com; 田园(1996—),女,陕西汉中人,硕士研究生,研究方向:最优化方法、理论与应用,E-mail: tianyuan_ty96@163.com; 刘雪(1995—),女,陕西延安人,硕士研究生,研究方向:最优化方法、理论与应用,E-mail: 1597553287@qq.com; 赵彦霖(1997—),男,河南人,硕士研究生,研究方向:最优化方法、理论与应用,E-mail: 756749010@qq.com。
  • 基金资助:
    国家自然科学基金资助项目(61763046, 62041212); 陕西省自然科学基础研究计划项目(2020JM-548)

An Improved Grey Wolf Algorithm for Flexible Job Shop Scheduling Problem

  1. (School of Mathematics and Computer Science, Yan’an University, Yan’an 716000, China)
  • Online:2022-08-22 Published:2022-08-22

摘要: 柔性作业车间调度问题是智能制造领域的一类典型调度问题,它是制造流程规划和管理中最关键的环节之一,有效的求解方法对提高生产效率具有重要的现实意义。本文基于经典灰狼算法进行改进,以优化最大完工时间为目标,提出一种改进的灰狼算法来求解柔性作业车间调度问题。算法首先采用基于权值的编码形式,实现对经典狼群算法中连续性编码的离散化;其次在迭代优化过程中加入随机游走策略,以增强局部搜索能力;然后在种群更新过程中加入尾部淘汰策略,在避免局部优化的同时增加种群多样性,合理扩大算法的广度搜索范围。在标准算例上的仿真实验结果表明,改进的灰狼算法在求解FJSP时比经典灰狼算法在寻优能力方面具有明显的优势,相比其它智能优化算法,本文所提算法在每种算例上均具有更好的优化性能。

关键词: 柔性作业车间调度, 最大完工时间, 灰狼优化算法, 随机游走, 局部搜索

Abstract: Flexible job shop scheduling problem is a typical scheduling problem in the field of intelligent manufacturing. It is one of the most key links in manufacturing process planning and management. An effective solution method is of great practical significance to improve production efficiency. Based on the classical grey wolf algorithm, an improved grey wolf algorithm is proposed to solve the flexible job shop scheduling problem with the goal of optimizing the makespan. Firstly, the algorithm adopts the weight based coding form to discretize the continuous coding in the classical wolf swarm algorithm. Secondly, the random walk strategy is added in the iterative optimization process to enhance the local search ability, then the tail elimination strategy is added in the population updating process to avoid local optimization, increase the population diversity and reasonably expand the search range of the algorithm. The simulation results on the standard example show that the improved wolf swarm algorithm has obvious improvement in the optimization ability than the classical grey wolf algorithm. Compared with other intelligent optimization algorithms, the algorithm proposed in this paper has better optimization performance in each example.

Key words: flexible job shop scheduling, makespan, grey wolf optimization algorithm, random walk, local search