Complexity of the job insertion problem in multi-stage scheduling
| Autor: | Gerhard J. Woeginger, Arjen P. A. Vestjens, Marc Wennink |
|---|---|
| Přispěvatelé: | Combinatorial Optimization 1 |
| Jazyk: | angličtina |
| Rok vydání: | 2007 |
| Předmět: |
Mathematical optimization
ComputingMilieux_THECOMPUTINGPROFESSION Job shop scheduling Computational complexity theory Computer science Applied Mathematics Scheduling (production processes) Flow shop scheduling Management Science and Operations Research Industrial and Manufacturing Engineering Job queue Multi stage Algorithm Software |
| Zdroj: | Operations Research Letters, 35(6), 754-758. Elsevier |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/j.orl.2007.02.004 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect