An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem

• Published in: Swarm and evolutionary computation 2022-03, Vol.69, p.100992, Article 100992
• Main Authors: Qin, Hao-Xiang, Han, Yu-Yan, Zhang, Biao, Meng, Lei-Lei, Liu, Yi-Ping, Pan, Quan-Ke, Gong, Dun-Wei
• Format: Article
• Language: English
• Subjects: Blocking; Energy efficiency; Hybrid flow shop scheduling problem; Iterated greedy algorithm; Local perturbation
• ISSN: 2210-6502
• DOI: 10.1016/j.swevo.2021.100992

•A mathematical model of a blocking hybrid flow shop scheduling problem with energy consumption criteria is proposed.•A simple global perturbation based on a half-swap operator is proposed to further search for the potentially best solution.•A local perturbation strategy based on a swap operator is designed to ensure the convergence of the algorithm.•The proposed algorithm is applied to 140 test instances with different scales and compared with state-of-the-art algorithms and can obtain the best solution to the BHFSP. With the continuous development of national economies, problems of various energy consumption levels and pollution emissions in manufacturing have attracted attention from researchers. Most existing research has focused on reducing economic costs and energy consumption. However, the Hybrid Flow Shop Scheduling Problem with energy-efficient criteria has not yet been well studied, especially with blocking constraints. This paper is the first to present a mathematical model of the blocking hybrid flow shop problem with an energy-efficient criterion and a modified Iterative Greedy algorithm based on a swap strategy designed to optimize the constructed model. In the proposed algorithm, first, a heuristic is adopted to generate the initial solution. Second, a local perturbation strategy based on a swap operator is designed to ensure the convergence of the algorithm. Third, a simple global perturbation strategy based on a half-swap operator is proposed as a means to further search for the potentially best solution with the traditional simulated annealing criterion. The proposed algorithm is applied to 150 test instances at different scales and compared to state-of-the-art algorithms. The experimental results demonstrate that the proposed algorithm outperforms the compared algorithms and can obtain a better solution.