An Discrete Differential Evolution And Its Application Research In Flexible Job-shop Scheduling Problem

Shop scheduling is the key of enterprise production management, with the aim of allocatingkinds of available resources reasonably, in order to meet specific goals or performance in theproduction process. Flexible job-shop scheduling is a complex Np-hard problem, and due toreduction of machine constraints, making it more in line with actual production environment.Meanwhile, actual production optimization often contains several objectives, and with thedevelopment of more varieties, small batch production mode, research in multi-objective, batchscheduling is of significant importance. This paper focuses on the application research ofdifferential evolution in flexible job-shop scheduling, make an effort to single-objective,multi-objective, and multi-objective batch scheduling problem, and the main contents aresummarized as follows:(1) Discussion the application of differential evolution algorithm in single-objective flexiblejob-shop scheduling. A flexible job-shop scheduling model is addressed with objective ofminimizing makespan. The algorithm is based on a parallel chromosome representation whichincludes job permutations and machine allocation for the problem. Dynamic random searchtechnique is introduced into the algorithm, and two local search strategies, including dynamicsearch based on critical path and machine load balancement, is designed to enhance the globaloptimization and local search capability. Experimental results show that the proposed algorithmcan effectively avoid local convergence.(2) Considering that more than one objective is existed in actual production process, amulti-objective discrete differential evolution based on Pareto dominate relationship is proposedfor multi-objective flexible job-shop scheduling. The algorithm adopts Pareto non-dominatesorting and crowd selection to select the next generation, and adopts external archive to savenon-donimated solutions found in evolution period. Simulation results indicate that the proposedalgorithm can obtain more Pareto non-dominate solutions with uniform distribution. (3) As to multi-objective flexible job-shop batch scheduling problem, a new batch splittingmethod based on demand and a new batch chromosome representation is put forward. A parallelchromosome representation is adopted to solve batch splitting and batch scheduling. Simulationon test examples show that the proposed algorithm can effectively reduce makespan and achievemore non-dominate solutions. Finally, the algorithm is applied to dyeing shop schedulingproblem.Finally, the research work of this paper is summarized and prospected.