Research And Application Of Open Shop Scheduling Problem

In the increasingly fierce competition environment,efficient shop scheduling is more and more important for manufacturing enterprises,and gradually become a key factor that affects the competitiveness of enterprises.Open Shop Scheduling Problem(OSSP)is one of a large number of production scheduling problems.It belongs to a class of important issues in the field of scheduling research and operations research.It has extensive application and research background.Firstly,the research status and research methods of traditional OSSP and Flexible Open Shop Scheduling Problem(FOSSP)are introduced systematically.At the same time,the research status and basic principles of two algorithms of Memetic Algorithm(MA)and Quantum Genetic Algorithm(QGA)are described.Secondly,aiming at the traditional OSSP,two mathematical models of the problem is established,and a MA to solve this problem is proposed.This algorithm not only follows the basic operation of the genetic algorithm,but also adds local search strategy based on it.After each crossover and mutation operation of GA,it performs local search through hill-climbing algorithm.By optimizing the distribution of population,timely deleting bad individuals,and then reduce the number of iterations to speed up the algorithm to solve the speed,not only ensures a high convergence of the algorithm,but also ensure that the solution obtained is high quality.Combining 40 sets of standard instance test experiments,and the comparison between the experimental results proved that the MA is effective in solving the traditional OSSP.Thirdly,the FOSSP is an extension to the traditional OSSP,which is closer to the actual scheduling problem.Aimed at the characteristics of FOSSP,a Modified Quantum Genetic Algorithm(MQGA)is proposed to minimize the manufacturing period as the objective function.The algorithm uses two coding sequences based on quantum bit coding to represent the population.The population evolution is realized by the quantum gate phase dynamic rotation strategy,and the diversity of the population is maintained by the catastrophic operation.The experiments were carried out based on the different work pieces and machine scale.The effectiveness of MQGA algorithm is verified by comparing the results of relative percentage deviation and two different density algorithms.Then,a set of prototype system of smart detection intelligent scheduling for open shop is designed,the main function modules of the system are briefly described,and the operation interface of some prototype systems is given.Finally,summarize the contents of the full text,and make prospects for future research directions of the open shop scheduling problem.