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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Borovkov A.A. (1998) Probabilities Theory. Amsterdam: Gordon and Beach.
Koryakin R.A. (2003) On the Stochastic Open Shop Problem. A. Albrecht, K. Steinhöfel (Eds.) Stochastic Algorithms: Foundations and Applications, Springer Verlag, 117–124
Potts C.N. et al. (1995) The Two Stage Assembly Scheduling Problem: Complexity and Approximation. Oper. Res. 43, 346–355
Sevastianov S.V. (1995) Vector Summation in Banach Space and Polynomial Time Algorithms for Flow Shops and Open Shops. Math. of Oper. Res. 20, 90–103
Sevastianov S.V. (1998) Nonstrict Vector Summation in Multi-Operation Scheduling. Annals of Oper. Res. 83, 179–211
Yurinsky V. (1995) Sums and Gaussian Vectors. Lecture Notes in Math. 1617, Springer Verlag
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koryakin, R. (2005). On Asymptotic Optimality of Permutation Schedules in Stochastic Flow Shops and Assembly Lines. In: Fleuren, H., den Hertog, D., Kort, P. (eds) Operations Research Proceedings 2004. Operations Research Proceedings, vol 2004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-27679-3_25
Download citation
DOI: https://doi.org/10.1007/3-540-27679-3_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24274-1
Online ISBN: 978-3-540-27679-1
eBook Packages: Business and EconomicsBusiness and Management (R0)