Article ID: | iaor20133942 |
Volume: | 206 |
Issue: | 1 |
Start Page Number: | 425 |
End Page Number: | 448 |
Publication Date: | Jul 2013 |
Journal: | Annals of Operations Research |
Authors: | Mnch Lars, Buscher Udo, Shen Liji |
Keywords: | batching, iterative methods, neighborhood search, parallel machines |
In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling.