Two-machine flow shop no-wait scheduling with machine maintenance

We study a two-machine flow shop scheduling problem with no-wait in process, in which one of the machines is subject to mandatory maintenance. The length of the maintenance period is defined by a non-decreasing function that depends on the starting time of that maintenance. The objective is to minimize the completion time of all activities. We present a polynomial-time approximation scheme for this problem. Received: November 2004 / Received version: March 2005 AMS classification: 90B35, 90B30, 90C59 The research was partly supported by INTAS (Project 03-51-5501) All correspondence to: Vitali A. Strusevich