Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (12): 325-333.DOI: 10.3778/j.issn.1002-8331.2307-0216

• Engineering and Applications • Previous Articles     Next Articles

Hybrid Beluga Whale Optimization Algorithm for Flexible Job Shop Scheduling Problem

MENG Guanjun, HUANG Jiangtao, WEI Yabo   

  1. School of Mechanical Engineering, Hefei University of Technology, Hefei 230009, China
  • Online:2024-06-15 Published:2024-06-14

混合白鲸优化算法求解柔性作业车间调度问题

孟冠军,黄江涛,魏亚博   

  1. 合肥工业大学 机械工程学院,合肥 230009

Abstract: In response to the flexible job-shop scheduling problem (FJSP), this paper proposes a hybrid beluga whale optimization algorithm (HBWO) to solve it, with the objective of minimizing the maximum completion time. Firstly, the standard beluga whale optimization algorithm (BWO) is improved with existing strategies to accelerate its convergence speed. Secondly, a two-level encoding scheme is designed based on the machine selection and operation sequencing problems to address the discretization issue of FJSP. Then, an active encoding and population initialization strategy is employed to enhance the solution quality. Subsequently, key paths and blocks are determined based on the start and end times of processes, with emphasis on various process time dimensions. The introduction of a greedy approach into the key-path-based hybrid variable neighborhood search strategy is aimed at expanding the exploration of the search space while reducing ineffective searches. Additionally, genetic operators are introduced to prevent the algorithm from being trapped in local optima. Finally, through simulation experiments and analysis on 35 standard instances, the effectiveness of the proposed algorithm in solving the FJSP problem is demonstrated.

Key words: flexible job-shop, beluga whale optimization algorithm, maximum completion time, discrete location transformation, hybrid variable neighborhood search strategy, greedy thought

摘要: 针对柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP),提出一种混合白鲸优化算法(hybrid beluga whale optimization,HBWO)对其求解,旨在最小最大化完工时间。采用既定策略改进标准白鲸优化算法(beluga whale optimization,BWO),加快其收敛速度;基于机器选择和工序排序问题设计双层编码方案,解决FJSP离散化问题;采用主动编码及种群初始化策略,提高求解质量;基于工序的开始和结束时间确定关键路径和关键块,注重各工序时间维度;引入贪心思想至基于关键路径的混合变邻域搜索策略中,加大勘测搜索空间及减少无效搜索;此外,引入遗传算子防止算法陷入局部最优;通过35个标准算例的仿真实验与分析,证明了算法在求解FJSP问题中具有有效性。

关键词: 柔性作业车间, 白鲸优化算法, 最大完工时间, 离散位置转化, 混合变邻域策略, 贪心思想