|
|||||
|
|
Complexity of the job insertion problem in multi-stage scheduling |
|
| Authors: | Arjen P.A. Vestjens |
| Affiliation: | a Centre for Quantitative Methods CQM BV, Postbus 414, 5600 AK Eindhoven, The Netherlands b BT Research, Sirius House 140, Adastral Park, Martlesham Heath, Suffolk IP5 3RE, UK c Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| 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: | Scheduling Computational complexity |
| 本文献已被 ScienceDirect 等数据库收录！ | |