Two-machine flow shop and open shop scheduling problems with a single maintenance window

The paper considers the two-machine flow shop and open shop scheduling problems to minimize the makespan, provided that one of the machines is subject to maintenance, which has to start within a prescribed time window. In the case of the flow shop, maintenance is performed on the second machine. A non-resumable setting is considered, i.e., if a job cannot be completed prior to the maintenance, it must restart from scratch after the maintenance. For each of these NP-hard problems we develop a 3/2-approximation algorithm.