A Hybrid Quantum-Inspired Genetic Algorithm for Flow Shop Scheduling

摘要

This paper is the first to propose a hybrid quantum-inspired genetic algorithm (HQGA) for flow shop scheduling problems. In the HQGA, Q-bit based representation is employed for exploration in discrete 0-1 hyperspace by using updating operator of quantum gate as well as genetic operators of Q-bit. Then, the Q-bit representation is converted to random key representation. Furthermore, job permutation is formed according to the random key to construct scheduling solution. Moreover, as a supplementary search, a permutation-based genetic algorithm is applied after the solutions are constructed. The HQGA can be viewed as a fusion of micro-space based search (Q-bit based search) and macro-space based search (permutation based search). Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the HQGA. The search quality of HQGA is much better than that of the pure classic GA, pure QGA and famous NEH heuristic.