Scheduling Three-Operation Jobs in a Two-Machine Flow Shop to Minimize Makespan

Jatinder Gupta, Christos Koulamas, George Kyparisis, Chris Potts () and Vitaly Strusevich

Annals of Operations Research, 2004, vol. 129, issue 1, 185 pages

Abstract: This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented. Copyright Kluwer Academic Publishers 2004

Keywords: scheduling; flow shop; makespan; approximation algorithm; polynomial time approximation scheme (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000030687.72169.c7 (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:spr:annopr:v:129:y:2004:i:1:p:171-185:10.1023/b:anor.0000030687.72169.c7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000030687.72169.c7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().