Paper Info
Title
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.
Year
DOI
Venue
2010
10.1080/0951192X.2010.495137
Int. J. Computer Integrated Manufacturing
Keywords
DocType
Volume
processing time,release time,batch processing machine,non-identical job size,ERT-LPT heuristic rule,ant colony optimisation ACO,ready time,parallel batch processing machine,dynamic job arrival,largest processing time,scheduling problem
Journal
23
Issue
ISSN
Citations 
10
0951-192X
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Huaping Chen126512.92
Bing Du200.34
George Q. Huang3876103.99