✦ LIBER ✦
Three is easy, two is hard: open shop sum-batch scheduling problem refined
✍ Scribed by Irina V. Gribkovskaia; Chung-Yee Lee; Vitaly A. Strusevich; Dominique de Werra
- Publisher
- Elsevier Science
- Year
- 2006
- Tongue
- English
- Weight
- 151 KB
- Volume
- 34
- Category
- Article
- ISSN
- 0167-6377
No coin nor oath required. For personal study only.
✦ Synopsis
For the two-machine open shop sum-batch problem to minimize the makespan an optimal schedule is known to contain one, two or three batches on each machine, and finding a two-batch optimal schedule is NP-hard. We adapt the open shop algorithm by de Werra for finding a three-batch optimal schedule in linear time.