Article ID: | iaor20072864 |
Country: | United States |
Volume: | 53 |
Issue: | 1 |
Start Page Number: | 16 |
End Page Number: | 23 |
Publication Date: | Feb 2006 |
Journal: | Naval Research Logistics |
Authors: | Schmidt G., Strusevich V.A., Breit J., Kubzin M.A. |
Keywords: | combinatorial analysis |
This paper addresses a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. The processing of an operation affected by a non-availability interval can be interrupted and resumed later. The objective is to minimize the makespan. We present two polynominal-time approximation schemes, one of which handles the problem with one non-availability on each machine and the other for the problem with several non-availability intervals on one of the machines. Problems with a more general structure of the non-availability intervals are not approximable in polynomial time within a constant factor unless