×

Probability masses Fitting in the analysis of manufacturing flow lines. (English) Zbl 1209.90149

Summary: 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.

MSC:

90B30 Production models
90B22 Queues and service in operations research

Software:

EMpht
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[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. · Zbl 1336.60035 · doi:10.1017/S0269964800004101
[2] Aldous, D., & Shepp, L. (1987). The least variable phase type distribution is Erlang. Stochastic Models, 3, 467–473. · Zbl 0635.60086 · doi:10.1080/15326348708807067
[3] Altiok, T. (1985). On the phase-type approximations of general distributions. IIE Transactions, 17(2), 110–116. · doi:10.1080/07408178508975280
[4] Altiok, T. (1996). Performance analysis of manufacturing systems. New York: Springer. · Zbl 0942.90003
[5] Asmussen, S., Nerman, A., & Olsson, M. (1996). Fitting phase-type distributions via the em algorithm. Scandinavian Journal of Statistics, 23, 419–441. · Zbl 0898.62104
[6] Baccelli, F., & Liu, Z. (1992). Comparison properties of stochastic decision free Petri nets. IEEE Transactions on Automatic Control, 37, 1905–1920. · Zbl 0772.60071 · doi:10.1109/9.182477
[7] Baccelli, F., & Makowski, A. M. (1989). Queueing models for systems with synchronization constraints. Proceedings of the IEEE, 77, 138–161. · doi:10.1109/5.21076
[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. · Zbl 1069.60013 · doi:10.1016/j.peva.2003.07.003
[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. · doi:10.1016/S0166-5316(03)00044-0
[11] Bobbio, A., Horváth, A., & Telek, M. (2005). Matching three moments with minimal acyclic phase type distributions. Stochastic Models, 21, 303–326. · Zbl 1069.60013 · doi:10.1081/STM-200056210
[12] Botta, R. F., & Harris, C. M. (1986). Approximation with generalized hyperexponential distributions: weak convergence results. Queueing Systems, 1(2), 169–190. · Zbl 0655.60012 · doi:10.1007/BF01536187
[13] Buzacott, J. A., & Shanthikumar, J. G. (1993). Stochastic models of manufacturing systems. Englewood Cliffs: Prentice-Hall. · Zbl 0769.90043
[14] Dallery, Y., & Frein, Y. (1993). On decomposition methods for tandem queueing networks with blocking. Operations Research, 41(2), 386–399. · Zbl 0771.90046 · doi:10.1287/opre.41.2.386
[15] Dallery, Y., & Gershwin, S. B. (1992). Manufacturing flow line systems: a review of models and analytical results. Queueing Systems, 12, 3–94. · Zbl 0782.90048 · doi:10.1007/BF01158636
[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. · doi:10.1145/185675.185776
[17] Gershwin, S. B. (1994). Manufacturing systems engineering. Englewood Cliffs: Prentice-Hall. · Zbl 0903.90070
[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. · Zbl 0171.16302 · doi:10.1287/opre.15.2.286
[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. · Zbl 0684.60012 · doi:10.1080/15326348908807131
[20] Kerbache, L., & MacGregor Smith, J. (1987). The generalized expansion method for open finite queueing networks. European Journal of Operational Research, 32, 448–461. · Zbl 0691.60088 · doi:10.1016/S0377-2217(87)80012-7
[21] Klincewicz, J. G., & Whitt, W. (1984). On approximations for queues, ii: Shape constraints. AT&T Bell Laboratories Technical Journal, 63(1), 139–161. · Zbl 0598.90041
[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. · Zbl 0872.60071
[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. · Zbl 04563211 · doi:10.2307/2685775
[24] Marie, R. (1980). Calculating equilibrium probabilities for {\(\lambda\)}(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. · doi:10.2307/2684718
[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. · doi:10.1016/j.peva.2005.06.002
[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. · Zbl 0912.90159 · doi:10.1016/0377-2217(95)00378-9
[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. · Zbl 0444.62024 · doi:10.1080/03610917908812115
[29] Perros, H. G. (1994). Queueing networks with blocking: exact and approximate solutions. Oxford: Oxford University Press. · Zbl 0849.90064
[30] Sauer, C. H., & Chandy, K. M. (1975). Approximate analysis of central server models. IBM Journal of Research and Development, 19(3), 301–313. · Zbl 0302.68080 · doi:10.1147/rd.193.0301
[31] Schmickler, L. (1992). Meda: mixed Erlang distributions as phase-type representations of empirical distribution functions. Stochastic Models, 8(1), 131–156. · Zbl 0749.60012 · doi:10.1080/15326349208807217
[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 . · Zbl 1176.90185
[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. · Zbl 0561.65007 · doi:10.1137/0906003
[36] Whitt, W. (1982). Approximating a point process by a renewal process, i: Two basic methods. Operations Research, 30(1), 125–147. · Zbl 0481.90025 · doi:10.1287/opre.30.1.125
[37] Whitt, W. (1984). On approximations for queues, i: Extremal distributions. AT & T Bell Laboratories Technical Journal, 63(1), 115–138. · Zbl 0598.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.