Modified Quantum Evolutionary Algorithms For Scheduling Problems

Effective production scheduling is an important means to improve production efficiency and economic benefit for an modern enterprise, but the existing literatures using quantum evolutionary algorithms to research production scheduling problem is very limited. In terms of research contents,only flow shop scheduling problems and stochastic job shop scheduling problems has been researched.However,the more realistic and complex scheduling problems such as flexible job-shop problem,machine scheduling problems with deterioration and multiple objective scheduling problems,etc have not been studied by quantum evolutionary algorithm so far. In terms of research methods, quantum coding and decoding method and quantum population evolutionary methods are worth further improvement. Since quantum theory was introduced in genetic algorithm,quantum intelligent computing has achieved remarkable progress. Current research results include quantum neural network algorithm,quantum genetic algorithm,quantum annealing algorithm,quantum particle swarm optimization, quantum cloning algorithm,quantum immune algorithm,quantum clustering algorithm and quantum wavelet algorithm, etc. Among various kinds of algorithm, quantum coding and decoding method and quantum evolutionary method plays an important role on the performance of the algorithms. The main evolution way of various algorithms has quantum not gate, quantum rotation gate and all kinds of hybrid evolutionary method, in which quantum gate is a widely adopted method. In most of the literatures, the quantum rotation angle are fixed constant, that is to say,it has nothing to do with the changing objective function value.Therefore, it is a important subject that how to apply quantum evolutionary algorithm to research scheduling problems.In the paper, the characteristic of quantum evolutionary algorithm were researched.Noval quantum evolutionary algorithms for flow-shop scheduling problem,job-shop scheduling problem and flexible job-shop scheduling problem were proposed,respectively.In the noval algorithms,different encoding and decoding mechanism for different scheduling problems were given.At the same time, different evolutionary method for different scheduling problems were provided.The effectiveness of the noval algorithms were demonstrated by being simulated to many benchmark problems.At last,the future development direction of the quantum evolutionary algorithm was prospect.The main contributions of this dissertation can be summarized as follows:(1) It comprehensively summarizes the importance of the production scheduling and the descriptions of all kinds of production scheduling problems. It provides all kinds of classification method for scheduling problems. The characteristics of all kinds of scheduling problems are analysed. It comprehensively summarizes various kinds intelligent computing algorithms.It also gives the performance index and classification solutions of scheduling problems.The development process and research strategies of scheduling problems are reviewed in the dissertation.The fundamental theory of quantum computing is explained and the development process and main computing method of quantum computing are exposed.It sketch out the principal theory of quantum intelligent computing and summarizes the achievement in the recent years,especially the appications in production scheduling problems(2) NHQGA is proposed based on HQGA for flow shop scheduling problems.In the novel algorithm,new encoding and decoding method and quantum evolutionary strategy are presented.A shorter quantum chromosome in the noval algorithm is proposed in order to improve the optimization effectiveness and optimization speed. There are a marked improvement in optimization effectiveness and optimization speed by means of simulating many benchmark flow-shop problems.(3) A novel quantum evolutionary algorithm, called jumping gene quantum evolutionary algorithm(JGQEA), is proposed for job shop scheduling problem with the objective to minimize the makespan.JGQEA is based on the quantum evolutionary algorithm and introduced in jumping operator, which inspired by the concept of jumping genes (transposons) in natural genetics. The effectiveness and the applicability of JGQEA are demonstrated by simulational results on the job shop scheduling problems. The results show that JGQEA is superior to QEA as well as other evolutionary algorithms.(4) A quantum evolutionary algorithm is proposed for flexible job-shop scheduling problems with the objective to minimize the makespan. We design an encoding method based on working procedures and a decoding method based on machines according on the feature of the flexible job-shop scheduling problems in the algorithm.Dynamic rotation angle and jumping gens operator are introduced. The effectiveness and the applicability of the algorithm are demonstrated by simulational results on the flexible job-shop scheduling roblems. (5) The opening problems of quantum evolutionary algorithm in production scheduling is summarized,and the future research directions are prospected.