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. © 2010 Taylor & Francis.