| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143151 | Operations Research Letters | 2007 | 5 Pages |
Abstract
The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Arjen P.A. Vestjens, Marc Wennink, Gerhard J. Woeginger,