Discrete Differential Evolution Algorithm For Job Shop Scheduling Problem

Scheduling is a decision-making process, it plays an important role in manufacturing and production systems. Job shop scheduling problem is a kind of very important production scheduling problem, it has a widely practical application background. However, job shop scheduling is a typical combinatorial optimization problem, which has a NP hard characteristic.Although people have proposed many kinds of scheduling algorithms, due to the complexity of the scheduling problem and the application environment, it is necessary to further research on it.The differential evolution algorithm is a swarm intelligence optimization algorithm, it does a parallel and random search operation. It has the advantages of fast convergence and high accuracy in the optimization of large scale problems. Based on the efficient performance,and aim to its continuous characteristics, when applied the algorithm to solve the scheduling problem, it is necessary to be discretized firstly. So the thesis improved a discrete differential evolution algorithm with the characteristics of job shop scheduling and deeply research on the algorithm, then apply it on the job shop scheduling problem and the distributed job shop scheduling problem.Aim to solve job shop scheduling problem, the thesis made two changes with study the research status at home and abroad and in-depth analysis of the structural characteristics of the problem and the algorithm. Firstly, the adaptive mutation factor is adopted. The adaptive mutation factor can adjust the algorithm according to the number of iterations, at the initial stage guaranteed the diversity of the population and in the later period avoided the blind change of the optimal solution. Secondly, according to the basic principle of the crossover operation, to re select each of individual by changing the way of providing parents, to make the cross operation can directly generate a feasible scheduling solution. For distributed job shop scheduling, based on the discrete differential evolution algorithm, this thesis increases the selection operation of the factory.In order to verify the feasibility of the proposed algorithm, the algorithm proposed in this thesis is denoted as DE1, and denote the algorithm DE2 that make the infeasible solutions to feasible random.In this thesis, VC++6.0 and MATLAB are used as simulation environment. Firstly, the differential evolution algorithm is realized by using the MATLAB rich library functions. For generate the Gantt chart of the job shop scheduling problem, due to the huge amount of computation, using the mex file to called the C language, with the operation ability of it to shorten the simulation time of the algorithm. Use the algorithm to simulate the FT06、 FT10、LA01、LA06、LA11 and distributed job shop scheduling problems. Through results proved the proposed discrete differential evolution algorithm is feasible and efficient.