Research On Multi-objective Batch Scheduling On Parallel Machines With Non-identical Job Sizes Using Intelligent Optimization Algorithms

The production scheduling problem refers to the reasonable allocation of the shared resources, the appropriate sequence of production plans in a certain period of time. Reasonable scheduling scheme will greatly improve the efficiency of resource utilization and production efficiency, reduce the production cost. This will make the enterprise more competitive, and promote the development of the society.As one of the important branches of classical scheduling problems, batch scheduling has become a hotspot due to its great practical and theoretical value. Although the research of production scheduling has the important significance to manufacturing industries, a lot of scheduling problems have not been effectively solved, because the real problems are often multi-constraint, multi-objective, and uncertain. Many of them have been proved to be NP-hard and thus it is hard to find the optimal solution. Because of the features of complexity and high dimensions, multi-objective batch scheduling with non-identical job sizes has not been solved effectively.In this thesis, the basic concepts of scheduling problem are firstly introduced such as the three-parameter method to describe the scheduling problems and the classification of scheduling problems. Next the current research status of the batch scheduling problems, from the single machine, the parallel machines and the shop environments, and the existing problems are analyzed.Then, the related concepts of multi-objective optimization problems are presented, especially those of multi-objective optimization methods based on Pareto. The bicriteria batch scheduling problems on parallel machines which considered the assignment cost of the jobs are discussed. However, the research on parallel batching scheduling focuses on how to improve the production efficiency, that is, study how to optimize the objectives related to the processing times. Moreover, the studied cost objectives are generally the delivery cost while the cost generated during allocating and processing periods is ignored. Hence, the bicriteria batching scheduling problem considering both the processing-time objectives and the cost objectives is studied.The problem is solved in two steps. Firstly the jobs are batched into different batches by BFLPT rule; and then, the batches are scheduled by three different evolutionary algorithms, i.e., NSGA-Ⅱ, SPEA2and the Improved-NSGA-II. The last one is an improved algorithm based on NSGA-Ⅱ incorporated a heuristic into the process of iterating the population to obtain the better Pareto set. After the preliminary experiments for determining the parameters of the evolutionary algorithms, the simulation experiments are conducted to verify and compare the three algorithms from three aspects, i.e., the size and quality of the Pareto set and running time. The experimental results show that the Improved-NSGA-Ⅱ algorithm outperform the other two in number and quality of Pareto solutions.