Metaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivals

Abstract

Batch processing machines that can process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This research investigates the scheduling problem on parallel batch processing machines in the presence of dynamic job arrivals and non-identical job sizes. The processing time and ready time of a batch are equal to the largest processing time and release time among all jobs in the batch, respectively. 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 genetic algorithm (GA) and an ant colony optimisation (ACO) are further proposed using ERT-LPT to minimise makespan. The performances of the two approaches, along with a BFLPT-ERTLPT (BE) heuristic were compared by computational experiments. The results show that both metaheurisitcs outperform BE. GA is able to obtain better solutions when dealing with small-job instances compared to ACO, whereas ACO dominates GA in large-job instances.

Keywords:

• batch scheduling
• makespan
• dynamic job arrivals
• genetic algorithm
• ant colony optimisation

Acknowledgements

The authors would like to thank Xiaolin Li, Qi Tan, and Song Zhang for technical assistance. This work was supported by the National Natural Science Foundation of China (70821001), Research fund for the Doctoral program of Higher Education of China (200803580024), HKSAR ITF (GHP/042/07LP) and HKSAR RGC GRF (HKU 712508E).