Article ID: | iaor20041016 |
Country: | Germany |
Volume: | 57 |
Issue: | 2 |
Start Page Number: | 217 |
End Page Number: | 234 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Methods of Operations Research (Heidelberg) |
Authors: | Schmidt G., Strusevich V.A., Breit J. |
We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.