| Article ID: | iaor201112775 |
| Volume: | 58 |
| Issue: | 7 |
| Start Page Number: | 676 |
| End Page Number: | 684 |
| Publication Date: | Oct 2011 |
| Journal: | Naval Research Logistics (NRL) |
| Authors: | Mosheiov Gur, Oron Daniel |
| Keywords: | scheduling, simulation: applications, heuristics |
The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs (m ≥ 3) is known to be strongly NP-hard even with no setup times. We focus in this article on the two-machine case. We assume UET jobs and consider batching with batch availability and machine-dependent setup times. We introduce an efficient (O(√n)) algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances.