To Solve the Job Shop Scheduling Problem with the Improve Quantum Genetic Algorithm

摘要

Job shop scheduling problem has been a typical scheduling problem that has been thoroughly studied over the last few decades. It has been proven to be a NP-hard problem. The purpose of job scheduling is to assign the work pieces to each machine according to a certain sequence and accomplish the work process with the minimum time. This paper, based on the quantum algorithm theory and quantum chromosome coding knowledge as well as the traditional genetic algorithm, raises an improve quantum genetic algorithm for job shop scheduling. Under the process expression form, it suggests to present the codes as quantum chromosome in order to solve the job shop scheduling problem and make it easy for the information of the elitist to be used to control the variation and make the population to evolve towards the excellent pattern with a large probability and accelerate the convergence rate. The simulation results indicate that the algorithm has better searching and convergence performances.