Batch scheduling on a two‐machine jobshop with machine‐dependent setup times |
| |
| Authors: | Gur Mosheiov Daniel Oron |
| |
| Institution: | 1. School of Business Administration, The Hebrew University of Jerusalem, Jerusalem 91905, Israel;2. School of Business, The University of Sydney, NSW 2006, Australia |
| |
| Abstract: | 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 \begin{align*}(O(\sqrt{n}))\end{align*} 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. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011 |
| |
| Keywords: | batch scheduling jobshop setup‐time unit execution time jobs |
|
|
