Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (7): 251-256.DOI: 10.3778/j.issn.1002-8331.2001-0160

Previous Articles     Next Articles

Two-Vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem

XIE Ruiqiang, ZHANG Huizhen   

  1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2021-04-01 Published:2021-04-02

求解柔性作业车间调度问题的两段式狼群算法

谢锐强,张惠珍   

  1. 上海理工大学 管理学院,上海 200093

Abstract:

Aiming at the flexible job shop scheduling problem with the objective function of minimizing the maximum completion time, a two-stage wolf swarm algorithm is proposed. In order to ensure the quality of the initial solution, the two-vector code coding method is used to design the initialization population. By redesigning the walk behavior, call behavior and siege behavior in the original wolf swarm algorithm, the problem that the original wolf swarm algorithm is easy to fall into local optimum is solved. Then the distance decision factor in the original wolf swarm algorithm is abandoned to reduce the complexity of the algorithm. Finally, the simulation test and algorithm comparison of two examples in the workshop show the effectiveness of the proposed algorithm to solve the problem, and provide a more effective method for solving the flexible job shop scheduling problem.

Key words: two-vector wolf pack algorithm, flexible job shop scheduling, makespan

摘要:

针对以最小化最大完工时间为目标函数的柔性作业车间调度问题,建立其数学模型并提出了一种两段式狼群算法加以求解。采用两段式(two-vector code)的编码方式,设计初始化种群的方式,保证初始解的质量及多样性;通过对原始狼群算法中游走行为、召唤行为、围攻行为的重新设计,解决了原始狼群算法易陷入局部最优的问题;舍弃原始狼群算法中的距离判定因子,来降低算法的复杂度。对车间两个实例进行仿真测试和算法比较,验证了所提算法求解该问题的有效性,为其解决柔性作业车间调度问题提供了一种更加有效的方法。

关键词: 两段式狼群算法, 柔性作业车间调度, 最大完工时间