On Asymptotic Optimality of Permutation Schedules in Stochastic Flow Shops and Assembly Lines

Roman Koryakin ()
Additional contact information
Roman Koryakin: Sovolev Institure of Mathematics of SB RAS

A chapter in Operations Research Proceedings 2004, 2005, pp 200-206 from Springer

Abstract: Abstract For the stochastic flow shop problem with m machines, n jobs and operation processing times being independent identically distributed random variables, we consider permutation schedules — those in which each machine processes the jobs in the same order. For fixed m and increasing n, the asymptotic behavior of an arbitrary permutation schedule length is researched. Let T be the makespan of that schedule. Considering the maximum machine load L as a lower bound of the makespan, we show that for a wide class of operation processing time distributions the average-case ratio T/L converges to 1. Thus, an arbitrary permutation flow shop schedule is asymptotically optimal with n → ∞, and one can construct such schedule in a linear time. The same result is derived for the stochastic assembly line problem with m machines and n jobs.

Keywords: Assembly Line; Polynomial Time Algorithm; Flow Shop; Open Shop; Asymptotic Optimality (search for similar items in EconPapers)
Date: 2005
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:oprchp:978-3-540-27679-1_25

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

DOI: 10.1007/3-540-27679-3_25

Access Statistics for this chapter

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