Research On Job-Shop Scheduling Problem Based On Intelligent Optimization Algorithm

Job-Shop Scheduling Problem has been a very complicated combinatorial optimization problem, which was proved to be NP-hard. It had very vital significance in the project application. The research and application of effective production scheduling methods and optimization techniques were the key elements to implement advanced manufacture and promote production efficiency, and had been an attractive subject in academic and industrial communities.On the basis of the technical review on the domestic and foreign research, combining the actual job shop operation, an extensive and systematic study on Job-Shop Scheduling Problem was carried out in this thesis.Firstly, Job-Shop Scheduling Problem's conception, sorts, characteristics, research content, evaluative criteria and conventional algorithms were analyzed systematically. Particle Swarm Optimization (PSO) algorithm was introduced and researched systematically from its background, basic principle, solving process and improvements.Secondly, dealing with such disadvantages of PSO algorithm as finite sampling space, being easy to run into prematurity in the actual scheduling problem, Quantum-behaved Particle Swarm Optimization (QPSO) algorithm was proposed to be applied to solve Job-Shop Scheduling Problem. On the base of analyzing QPSO basic theory and algorithm characteristics, this algorithm was applied to solve Job-Shop Scheduling Problem by the optimization target of minimum processing end time of all the parts and the working procedure coding method, and this algorithm could be used to optimize Job-Shop Scheduling Problem. And then the astringency and efficiency of the algorithm was proved through an application instance, and it was superior to Genetic Algorithm and PSO algorithm.Finally, because QPSO algorithm possibly run into prematurity, the mutation mechanism is introduced into QPSO algorithm to escape from local optima and strengthen its global search ability, QPSO algorithm with mutation operator was put forward, and then the better global astringency ability and efficiency of the algorithm was proved by optimizing a complex Job-Shop Scheduling Problem instance.The work in this paper indicate that QPSO and QPSO algorithm with mutation operator used for solving Job-Shop Scheduling Problem could generate better performance and more rapid convergence than other intelligent optimization algorithms such as Genetic Algorithm and PSO algorithm. It will work well on optimizing Job-Shop Scheduling Problem.