Three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines

S. S. Panwalkar () and Christos Koulamas ()
Additional contact information
S. S. Panwalkar: Johns Hopkins University
Christos Koulamas: Florida International University

Journal of Scheduling, 2020, vol. 23, issue 1, No 8, 145-154

Abstract: Abstract We show by induction that the shortest processing time sequence is optimal for a number of three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines, effectively proving the optimality of an index priority rule when the adjacent job pairwise interchange argument does not hold. We also show that when the middle machine is maximal, the synchronous flow, blocking and no-wait problems are equivalent, because they can be effectively decomposed into two equivalent two-stage problems. A similar equivalence is shown for the classical flow shop and the flow shop with no-idle machines. These equivalences facilitate the solution of one problem by using the optimal algorithm for the equivalent problem. Finally, we observe that when the middle machine is minimal, the optimal sequence is not a pyramid sequence for the synchronous flow and blocking flow shops. On the other hand, we show that the optimal sequence for the flow shop with no-idle machines is a pyramid sequence obtainable by dynamic programming in pseudo-polynomial time.

Keywords: Flow shop; Synchronous; Blocking; No-idle machines (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00618-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00618-6

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

DOI: 10.1007/s10951-019-00618-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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