The Two-Machine Flow Shop

Hamilton Emmons () and George Vairaktarakis ()
Additional contact information
Hamilton Emmons: Case Western Reserve University
George Vairaktarakis: Case Western Reserve University

Chapter Chapter 2 in Flow Shop Scheduling, 2013, pp 21-66 from Springer

Abstract: Abstract The two-machine flow shop has attracted significant attention, especially when it comes to extensions of the basic makespan model to include release times, setups, or other complications. As expected, we start our coverage with a full discussion of Johnson’s Rule for makespan minimization. Then, we present extensions that incorporate setup/teardown times in automated manufacturing cells. When arbitrary positive release times are assumed for jobs, the problem of minimizing makespan in the two-machine flow shop is shown to be NPcomplete, and hence we discuss solution procedures, optimal and heuristic. Even when a single server is used to perform setups, the problem is shown strongly NP-complete, though special cases accept simple solutions. Results on optimal lot streaming of a product are also presented. Precedence constraints are postponed to a later chapter. Subsequently, we survey results on objectives like ΣCj, Lmax, Tmax, ΣTj, ΣUj, as well as corresponding multicriteria. Various manifestations of these models come with setups, scarce resources, common deadlines, etc. Whenever possible, we provide dominance properties, lower bounds, branch-andbound approaches, heuristics and computational results.

Keywords: Completion Time; Optimal Schedule; Flow Shop; Total Completion Time; Total Tardiness (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:isochp:978-1-4614-5152-5_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461451525

DOI: 10.1007/978-1-4614-5152-5_2

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().