An effective co-evolutionary quantum genetic algorithm for the no-wait flow shop scheduling problem

Abstract

This article proposes a competitive co-evolutionary quantum genetic algorithm for the no-wait flow shop scheduling problem with the criterion to minimize makespan, which is a renowned NP-hard combinatorial optimization problem. An innovative coding and decoding mechanism is proposed. The mechanism uses square matrix to represent the quantum individual and adapts the quantum rotation gate to update the quantum individual. In the algorithm framework, the store-with-diversity is proposed to maintain the diversity of the population. Moreover, a competitive co-evolution strategy is introduced to enhance the evolutionary pressure and accelerate the convergence. The store-with-diversity and competitive co-evolution are designed to keep a balance between exploration and exploitation. Simulations based on a benchmark set and comparisons with several existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm.