Polynomial‐time approximation schemes for two‐machine open shop scheduling with nonavailability constraints

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 polynomial‐time approximation schemes, one of which handles the problem with one non‐availability interval 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 . © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006