| Article ID: | iaor2007673 |
| Country: | Netherlands |
| Volume: | 34 |
| Issue: | 4 |
| Start Page Number: | 459 |
| End Page Number: | 464 |
| Publication Date: | Jul 2006 |
| Journal: | Operations Research Letters |
| Authors: | Lee Chung-Yee, Strusevich Vitaly A., Werra Dominique de, Gribkovskaia Irina V. |
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.