A single-individual based variable neighborhood search algorithm for the blocking hybrid flow shop group scheduling problem

Abstract

The Blocking Hybrid Flow Shop Group Scheduling Problem (BHFGSP) is prevalent within the manufacturing industry, where the ordering of groups poses a significant challenge for dispatchers. Moreover, the blocking constraints associated with jobs significantly influence energy consumption, yet these constraints are often overlooked in algorithm design. To address these issues effectively, a single-individual-based variable neighborhood search strategy is introduced. For the challenge of group ordering, a group-based neighborhood search strategy is proposed. This strategy is complemented by a job-based neighborhood search strategy to tackle the issues of blocking and job sequencing. These two neighborhood search strategies are designed to enhance the performance of the algorithm significantly. Furthermore, to augment the local search abilities of the proposed algorithm, the concept of a single-individual approach from the iterated greedy algorithm is integrated. The performance of the proposed algorithm is validated through 36 instances, demonstrating its efficiency in solving BHFGSPs compared to state-of-the-art algorithms. Notably, the proposed algorithm achieves a reduction in energy consumption by an average of 58% to 63.4% compared to previous best solutions.

Keywords

• Hybrid flow shop group scheduling problem
• Blocking constraints
• Energy consumption
• Single-individual based algorithm
• Neighborhood search strategy