Quantum Representation Based Job Shop Scheduling
Kazi Shah Nawaz Ripon, Ashay Singh · 2023
This paper proposes a quantum representation-based genetic algorithm for solving the job-shop scheduling problem, aiming to minimize the makespan. The job-shop scheduling is a typical scheduling problem that falls under the NP-hard combinatorial optimization problems and has undergone extensive investigation in the literature. Over time, various heuristic and intelligent methods have been developed to tackle this challenging problem. Inspired by the promise of quantum computing, this paper explores using quantum information representation and processing techniques to enhance the performance of conventional genetic algorithms on classical computers to solve the job-shop scheduling problem. The proposed quantum-inspired genetic algorithm employs a conversion mechanism of quantum representation to code the schedule; and utilizes a rotation angle table to update the population. The effectiveness of the quantum-inspired genetic algorithm is compared to that of a standard genetic algorithm, with experimental results confirming the potential of the proposed approach in tackling complex combinatorial optimization problems.