The No-Wait Flow Shop

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

Chapter Chapter 6 in Flow Shop Scheduling, 2013, pp 189-220 from Springer

Abstract: Abstract After describing some real-world examples of flow shops with no waiting, we demonstrate the equivalence of no-wait and blocking in the shop with m = 2. For the no-wait shop, some research is available on the flow time objective while the majority of research focuses on the makespan objective. Hence, we start with a detailed discussion of an O(n log n) algorithm for F2|nwt|C max. For the makespan objective and m > 2 machines, we present a plethora of polynomially solvable special cases of the problem. Most interesting is the case with semi-ordered processing time matrices. In this case, a so called pyramidal schedule provides an optimal solution in O(n 2) time. Heuristic algorithms for m > 2 and the makespan objective show that the problem is intimately related to the traveling salesman problem. We survey the state of the art on metaheuristics. The problem is analyzed in the presence of lot streaming, with separable setup and teardown times, and in assemblytype and hybrid flow shops.

Keywords: Schedule Problem; Bipartite Graph; Travel Salesman Problem; Travel Salesman Problem; Flow Shop (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

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_6

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

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

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 ().