Hybrid quantum particle swarm optimization and variable neighborhood search for flexible job-shop scheduling problem

The rise and integration of Industry 4.0 has led to a growing focus on the flexible job-shop scheduling problem (FJSP). As an extension of the classic job-shop scheduling problem, FJSP is recognized as an NP-hard problem. Swarm intelligence algorithms provide a robust and adaptable approach for addressing the FJSP, generating approximate solutions near the optima within significantly less computing time. This study proposes a hybrid algorithm HQPSO-VNS that integrates quantum particle swarm optimization (QPSO) and variable neighborhood search (VNS) for efficiently addressing the FJSP. A chaotic encoding scheme suitable for QPSO is used to represent a scheduling solution. Nine new neighborhood structures are designed to increase the population diversity and local search capability of the algorithm. Additionally, to overcome the shortcoming in neighborhood disturbance, a new neighborhood transformation rule based on the length of the encoding sequence is developed. Finally, HQPSO-VNS and five state-of-the-art algorithms are tested on problem instances from Kacem, Brandimarte, and Dauzere-peres datasets, and an industrial case study. The experimental results indicate that HQPSO-VNS has faster convergence, better stability, and broader applicability.