Two-machine flow shops with limited machine availability

This paper studies a flow shop where machines have some periods of limited availability. The limited availability may be due to preschedules, preventive maintenance, or overlap of two consecutive time horizons in the rolling time horizon planning algorithm. It is shown that the problem of minimizing makespan in such a flow shop is NP-hard in the strong sense, and that no polynomial time heuristic with constant relative error exists for the problem unless P=NP. Some important properties of optimal schedules are proved for two-machine flow shops. A branch and bound algorithm based on these properties is proposed, and results of computational experiments with the algorithm are presented.