January 2001, Volume 52, Issue 1, Pages 116 - 121

Technical Note

Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability M-L Espinouse1, P Formanowicz2 & B Penz3 1LOSI, Université de Technologie de Troyes, France,     2Pozna University of Technology, Poland     3GILCO, ENSGI-INPG, France     Correspondence to: Dr M-L Espinouse, Université de Technologie de Troyes, Laboratoire d'Optimisation de Systèmes Industriels, 12, rue Marie Cure, BP 2060, 10 010 Troyes Cedex, France. E-mail: Marie-Laure.Espinouse@univ-troyes.fr

Keywords

scheduling;   flow shop;   complexity;   heuristics

Abstract

The scheduling problems studied in this paper concern a two-machine no-wait flow shop problem with limited machine availability. In this model, we assume that machines may not always be available, for example because of preventive maintenance. We only consider the deterministic case where the unavailable periods are known in advance. The objective function considered is the maximum completion time (Cmax). We prove that the problem is NP-hard even if only one non-availability period occurs on one of machines, and NP-hard in the strong sense for arbitrary numbers of non-availability periods. We also provide heuristic algorithms with error bounding analysis.

Received February 1999; Accepted May 2000

^© Macmillan Publishers Ltd 2001