A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan |
| |
Authors: | Onur Ozturk Gregory S. Zaric |
| |
Affiliation: | 1. Département Ingénierie des Systèmes, Université Paris-Est, ESIEE Paris, Noisy le Grand Cedex, France.;2. Ivey Business School, Western University, London, Canada. |
| |
Abstract: | In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution. |
| |
Keywords: | scheduling batch scheduling parallel machines makespan branch and bound heuristics mathematical programming |
|
|