The Research On A Single Batch-processing Machine With Non-identical Job Sizes Using Differential Evolution Algorithm

Scheduling problem is one of the most important combinatorial optimization problems. It is of great significance in industrial production, flexible manufacturing systems, modern logistics, computer science and other research fields. Batch scheduling is one kind of issue that is different from classical scheduling problems in which a number of jobs can be processed simultaneously in one machine. Batch scheduling problems with non-identical job sizes, where job sizes are not the same, is an important extension in this kind of scheduling problem. It is more complex than classical scheduling problem but close to real manufacturing circumstances. Therefore, not only research results but also economic prospect is promising.In this paper, we first introduce the background knowledge of scheduling. Then batch scheduling issues are listed with analysis of current research review. Mathematic model is proposed and studied. We also proposed several modified heuristic algorithms.This paper introduces the basic idea of differential evolution algorithm with detailed analysis of the advantage while dealing with continuous combinational optimization problems. Meantime, disadvantages in handling discrete problems are also analyzed. Based on the discrete characteristics of this kind of scheduling problems, crossover and mutation operations are re-designed in differential evolution algorithm. A novel differential evolution algorithm with iteration strategy is also proposed.A lot of experiments are implemented to determine the parameters in proposed novel differential evolution algorithm. Simulations are carried out to test the effectiveness of the algorithms. Compared to representative algorithms in classical scheduling such as simulation annealing and genetic algorithms, the performance of novel differential evolution algorithm is proved to be better.Suggestions and future research are presented in the last section.