New Hybrid Differential Evolution Algorithms For Production Scheduling Problem With Lot Streaming

Considering a job’s lot size greater than one in the real manufacturing environment, this dissertation studies production scheduling problem with lot streaming, which adapts to the batch production mode with the market’s diverse demands for various kinds of products in modern times. Lot splitting and lot scheduling are both involved in the problem, which makes it more complicated than traditional production scheduling problems, and motivated by practical applications, the problem has great theoretical and practical significance. On the basis of National Hi-tech Research and Development Program of China (863Program, Grant No.2007AA04Z155), National Natural Science Foundation of China (Grant No.60874074), and Zhejiang Provincial Hi-tech Research and Development Program of China (Grant No.2004C11011), this dissertation investigates scheduling methods based on Differential Evolution in the parallel machine, the Flow-shop and the Job-shop scheduling problems with lot streaming, making an effort to develop effective splitting and scheduling methods based on the characteristic of the specific problem. The main contributions of the dissertation are as follows:(1) The application of Differential Evolution is investigated in Parallel machine scheduling problem with lot splitting. According to the lot splitting constraint, an individual representation based on allocation arrays is proposed, and a new global search operator based on a block crossover method and a block mutation method is brought forward. A specific local search method is further designed based on the objective of minimizing the makespan, and thereby a hybrid Differential Evolution is propsed. Numerical experiments on the performance of the proposed algorithm on parallel machine scheduling problems with lot splitting covering identical and unrelated problem kinds and a realistic problem are performed, and the results indicate that the algorithm is feasible and efficient.(2) For the case of no interleaving of sublots from different products in a Flow-shop, the problem model of lot streaming in Flow-shop scheduling with non-intermingling sublots is established, and a hybrid Differential Evolution is proposed as the solution approach. A fast computation method of completion time is designed in the decoding procedure of the algorithm, and the evolution procedure of the algorithm includes DE/rand/1/bin global search method and an Insert-based local search method. Based on the lot scheduling solution obtained through the proposed algorithm, a heuristic lot splitting method is further designed to gain the lot splitting solution. The results of the simulation show the good performance of the proposed algorithm, and that the fast computation method of completion time and the heuristic lot splitting method can reduce the computation and the optimization burden.(3) The case where sublots from different products are allowed to interleave is considered in a Flow-shop, and the problem model with intermingling sublots and bounded sublot sizes is established. A hybrid Differential Evolution is proposed to split the original lot into many smaller processing sublots and find the optimal sequence of those sublots. The algorithm is based on a parallel chromosome representation, and the lot splitting chromosome and the lot scheduling chromosome are evolved according to the proposed two algorithms in the above sections respectively. To obtain a faster completion, the obtained processing sublots are further split into smaller transfer sublots during the decoding procedure of the algorithm. Experiments are done from three aspects, and the effectiveness of the algorithm and the splitting method are testified.(4) The job shop scheduling problem with lot streaming is studied under multiple-resource constraints, and the problem model is established based on equal-sized sublot. A new hybrid Differential Evolution algorithm is proposed to solve both the lot splitting problem and the lot scheduling problem based on a parallel chromosome representation, with a global search method based on self-adaptive Differential Evolution, and an Interchange-based local search method. The effectiveness of the proposed approach is testified through computational experiments of four test instances and a realistic problem in a speaker workshop.Finally, a production lot streaming scheduling system based on a B/S frame is developed on the basis of the above researches, and the feasibility and effectiveness of our proposed algorithms can be testified. And the research work of the whole dissertation is summarized and prospected.