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

Espinouse M-L (), P Formanowicz and B Penz
Additional contact information
Espinouse M-L: LOSI, Université de Technologie de Troyes
P Formanowicz: Poznań University of Technology
B Penz: GILCO, ENSGI-INPG

Journal of the Operational Research Society, 2001, vol. 52, issue 1, 116-121

Abstract: 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.

Keywords: scheduling; flow shop; complexity; heuristics (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601025 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:52:y:2001:i:1:d:10.1057_palgrave.jors.2601025

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601025

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().