Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability

Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability

0.00 Avg rating0 Votes
Article ID: iaor20013923
Country: United Kingdom
Volume: 52
Issue: 1
Start Page Number: 116
End Page Number: 121
Publication Date: Jan 2001
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: flowshop
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.

Reviews

Required fields are marked *. Your email address will not be published.