Probability masses fitting in the analysis of manufacturing flow lines

The analysis of manufacturing systems with finite capacity and with general service time distributions is made of two steps: the distributions have first to be transformed into tractable phase-type distributions, and then the modified system can be analytically modelled. In this paper, we propose a new alternative in order to build tractable phase-type distributions, and study its effects on the global modelling process. Called “probability masses fitting” (PMF), the approach is quite simple: the probability masses on regular intervals are computed and aggregated on a single value in the corresponding interval, leading to a discrete distribution. PMF shows some interesting properties: it is bounding, monotonic, refinable, it approximates distributions with finite support and it conserves the shape of the distribution. With the resulting discrete distributions, the evolution of the system is then exactly modelled by a Markov chain. Here, we focus on flow lines and show that the method allows us to compute upper and lower bounds on the throughput as well as good approximations of the cycle time distributions. Finally, the global modelling method is shown, by numerical experiments, to compute accurate estimations of the throughput and of various performance measures, reaching accuracy levels of a few tenths of a percent.

• metadata
• References
• relations

Document type	Article de périodique (Journal article)
Access type	Accès libre
Publication date	2011
Language	Anglais
Journal information	"Annals of Operations Research" - Vol. 182, no. 1, p. 163-191 (jan. 2011)
Peer reviewed	yes
Publisher	Springer Netherlands
issn	0254-5330
Publication status	Publié
Affiliations	Louvain School of Management - Operations and Information UCL - SSH/ILSM/ILSM - Research Institute of Louvain School of Management FUCaM - Sciences de gestion
Keywords	Manufacturing flow lines ; Probability masses fitting ; Discretization ; Bounds ; Performance measures ; Distributions
Links	http://hdl.handle.net/2078/115568[Handle] https://doi.org/10.1007/s10479-008-0512-1[DOI]

1. Adan, I. J., van Eenige, M. J., & Resing, J. A. (1995). Fitting discrete distributions on the first two moments. Probability in the Engineering and Informational Sciences, 9, 623–632.
2. Aldous, D., & Shepp, L. (1987). The least variable phase type distribution is Erlang. Stochastic Models, 3, 467–473.
3. Altiok, T. (1985). On the phase-type approximations of general distributions. IIE Transactions, 17(2), 110–116.
4. Altiok, T. (1996). Performance analysis of manufacturing systems. New York: Springer.
5. Asmussen, S., Nerman, A., & Olsson, M. (1996). Fitting phase-type distributions via the em algorithm. Scandinavian Journal of Statistics, 23, 419–441.
6. Baccelli, F., & Liu, Z. (1992). Comparison properties of stochastic decision free Petri nets. IEEE Transactions on Automatic Control, 37, 1905–1920.
7. Baccelli, F., & Makowski, A. M. (1989). Queueing models for systems with synchronization constraints. Proceedings of the IEEE, 77, 138–161.
8. Bobbio, A., & Cumani, A. (1992). Ml estimation of the parameters of a ph distribution in triangular canonical form. In G. Balbo & G. Serazzi (Eds.), Computer performance evaluation (pp. 33–46). Amsterdam: Elsevier.
9. Bobbio, A., Horváth, A., & Telek, M. (2004). The scale factor: a new degree of freedom in phase-type approximation. Performance Evaluation, 56(1–4), 121–144.
10. Bobbio, A., Horváth, A., Scarpa, M., & Telek, M. (2003). Acyclic discrete phase type distributions: properties and a parameter estimation algorithm. Performance Evaluation, 54, 1–32.
11. Bobbio, A., Horváth, A., & Telek, M. (2005). Matching three moments with minimal acyclic phase type distributions. Stochastic Models, 21, 303–326.
12. Botta, R. F., & Harris, C. M. (1986). Approximation with generalized hyperexponential distributions: weak convergence results. Queueing Systems, 1(2), 169–190.
13. Buzacott, J. A., & Shanthikumar, J. G. (1993). Stochastic models of manufacturing systems. Englewood Cliffs: Prentice-Hall.
14. Dallery, Y., & Frein, Y. (1993). On decomposition methods for tandem queueing networks with blocking. Operations Research, 41(2), 386–399.
15. Dallery, Y., & Gershwin, S. B. (1992). Manufacturing flow line systems: a review of models and analytical results. Queueing Systems, 12, 3–94.
16. Dallery, Y., Liu, Z., & Towsley, D. (1994). Equivalence, reversibility, symmetry and concavity properties in fork/join queueing networks with blocking. Journal of the ACM, 41, 903–942.
17. Gershwin, S. B. (1994). Manufacturing systems engineering. Englewood Cliffs: Prentice-Hall.
18. Hillier, F. S., & Boling, R. W. (1967). Finite queues in series with exponential or Erlang service times—a numerical approach. Operations Research, 15(2), 286–303.
19. Johnson, M. A., & Taaffe, M. R. (1989). Matching moments to phase distributions: Mixtures of Erlang distributions of common order. Stochastic Models, 5(4), 711–743.
20. Kerbache, L., & MacGregor Smith, J. (1987). The generalized expansion method for open finite queueing networks. European Journal of Operational Research, 32, 448–461.
21. Klincewicz J. G., Whitt W., On Approximations for Queues, II: Shape Constraints, 10.1002/j.1538-7305.1984.tb00006.x
22. Lang, A., & Arthur, J. L. (1997). Parameter approximation for phase-type distributions. In S. R. Chakravarthy & A. S. Alfa (Eds.), Matrix analytical methods in stochastic models (pp. 151–206). New York: Dekker.
23. Lindsay, B. G., & Basak, P. (2000). Moments determine the tail of a distribution (but not much else). The American Statistician, 54(4), 248–251.
24. Marie, R. (1980). Calculating equilibrium probabilities for λ(n)/ck/1/n queues. In PERFORMANCE ’80: Proceedings of the 1980 international symposium on computer performance modelling, measurement and evaluation (pp. 117–125). New York: ACM.
25. McCullagh, P. (1994). Does the moment-generating function characterize a distribution? The American Statistician, 48(3), 208.
26. Osogami, T., & Harchol-Balter, M. (2006). Closed form solutions for mapping general distributions to quasi-minimal ph distributions. Performance Evaluation, 63(6), 524–552.
27. Papadopoulos, H. T., & Heavey, C. (1996). Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines. European Journal of Operational Research, 92, 1–27.
28. Pearson, E. S., Johnson, N. L., & Burr, I. W. (1979). Comparisons of the percentage points of distributions with the same first four moments, chosen from eight different systems of frequency curves. Communications in Statistics–Simulation and Computation, 8(3), 191–229.
29. Perros, H. G. (1994). Queueing networks with blocking: exact and approximate solutions. Oxford: Oxford University Press.
30. Sauer, C. H., & Chandy, K. M. (1975). Approximate analysis of central server models. IBM Journal of Research and Development, 19(3), 301–313.
31. Schmickler, L. (1992). Meda: mixed Erlang distributions as phase-type representations of empirical distribution functions. Stochastic Models, 8(1), 131–156.
32. Tancrez, J.-S., & Semal, P. (2006). The bounding discrete phase-type method. In A. N. Langville & W. J. Stewart (Eds.), MAM 2006: Markov anniversary meeting (pp. 257–269). Raleigh: Boson.
33. Tancrez, J.-S., Semal, P., & Chevalier, P. (2008, in press). Histogram based bounds and approximations for production lines. European Journal of Operational Research. doi: 10.1016/j.ejor.2008.03.032 .
34. Telek, M. (2000). Minimal coefficient of variation of discrete phase type distributions. In 3rd international conference on matrix-analytic methods in stochastic models, MAM3 (pp. 391–400). Leuven: Notable Publications.
35. Varah, J. M. (1985). On fitting exponentials by nonlinear least squares. SIAM Journal on Scientific and Statistical Computing, 6(1), 30–44.
36. Whitt, W. (1982). Approximating a point process by a renewal process, i: Two basic methods. Operations Research, 30(1), 125–147.
37. Whitt W., On Approximations for Queues, I: Extremal Distributions, 10.1002/j.1538-7305.1984.tb00005.x

See also
	[boreal:12673]	Probability masses fitting in the analysis of manufacturing flow lines