Research On Models And Optimization Methods For Scheduling Batch Processing Machines

Scheduling on batch processing machines (BPM) is an important extension of classical scheduling problems. As a batch processing machine can process a group of jobs simultaneously, there are two interdependent decisions to be made for solving a BPM scheduling problem, i.e., forming batches and scheduling batches on BPM. Therefore, scheduling on BPM is much more complex than classical scheduling problems, and many of these BPM scheduling problems have been shown to be NP-hard.Batch processing machines are encountered in many real-world applications, such as burn-in operations in semiconductor industry, steel manufacturing and truck delivery. A good scheduling method may substantially improve production efficiency and reduce production cost, it is therefore of practical significance to study BPM scheduling problems.Although extensive work has been done in the past decades to address BPM scheduling issues, some significant aspects of BPM scheduling have not yet been sufficiently explored. To begin with, most previous work focused on the problems with identical job size, while non-identical job sizes have seldom been considered. Second, the approaches designed for BPM scheduling problems are mainly exact algorithms or simple heuristic rules, while complex constructive approaches are relatively fewer. Third, researchers in this field are mostly concerned with improving production efficiency such as minimizing makespan. However, energy efficiency issues in scheduling are of equal importance despite they have seldom been addressed.The lack of research in the above areas necessitates further investigations into BPM scheduling problems. In this study, the following work has been done:(1) The problem of scheduling BPM was considered from a clustering perspective. It was demonstrated that that minimizing makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimizing makespan was transformed into minimizing weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. Computational experiments showed the effectiveness of this algorithm.(2) The problem of scheduling BPM was extended to a parallel BPM environment. This problem is NP-hard in the strong sense, and hence two lower bounds were proposed to evaluate the performance of approximation algorithms. An ERT-LPT heuristic rule was next presented to assign batches to parallel machines. Two metaheuristics, a job sequence based genetic algorithm (GA) and an ant colony optimization (ACO) approach guided by heuristic information that was constructed using WRB are further proposed using ERT-LPT to minimize makespan. The performances of the two approaches were compared by computational experiments.(3) Energy efficiency was considered in a BPM scheduling problem. A new model was constructed to minimize makespan and electric power cost in a flexible flow shop with the presence of time-of-use electricity pricing. Three multi-objective optimization approaches, namely, preference vector ant colony system (PVACS), NSGA-II and SPEA2 based evolutionary algorithms were proposed and compared using different performance metrics.