Stochastic grey-box modeling of queueing systems: fitting birth-and-death processes to data

详细信息    查看全文

• 作者：James Dong (1)
  Ward Whitt (2)
  
  1. School of Operations Research and Information Engineering ; Cornell University ; 287 Rhodes Hall ; Ithaca ; NY ; 14850 ; USA
  2. Department of Industrial Engineering and Operations Research ; Columbia University ; New York ; NY ; 10027 ; USA
  
• 关键词：Birth ; and ; death processes ; Grey ; box modeling ; Fitting stochastic models to data ; Transient behavior ; First passage times ; Heavy traffic ; 60F17 ; 60J25 ; 60K25 ; 62M09 ; 90B25
• 刊名：Queueing Systems
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：79
• 期：3-4
• 页码：391-426
• 全文大小：1,049 KB
• 参考文献：1. Abate, J, Choudhury, GL, Whitt, W (1994) Waiting-time tail probabilities in queues with long-tail service-time distributions. Queueing Syst. 16: pp. 311-338 CrossRef
  2. Abate, J, Whitt, W (1994) A heavy-traffic expansion for the asymptotic decay rates of tail probabilities in multi-channel queues. Op. Res. Lett. 15: pp. 223-230 CrossRef
  3. Armony, M., Israelit, S., Mandelbaum, A., Marmor, Y., Tseytlin, Y., Yom-Tov, G.: Patient flow in hospitals: a data-based queueing-science perspective. New York University. Available at http://ie.technion.ac.il/serveng/References/ (2014). Accessed 19 Oct 2014
  4. Bhat, UN, Miller, GK, Rao, SS Statistical analysis of queueing systems. In: Dshalalow, JH eds. (1997) Frontiers in Queueing Theory. CRC Press, Boca Raton, FL, pp. 351-394
  5. Billingsley, P (1961) Statistical Inference for Markov Processes. University of Chicago Press, Chicago
  6. Bohlin, T (2006) Practical Grey-Box Process Identification. Springer, London
  7. Brown, L, Gans, N, Mandelbaum, A, Sakov, A, Shen, H, Zeltyn, S, Zhao, L (2005) Statistical analysis of a telephone call center: a queueing-science perspective. J. Am. Stat. Assoc. 100: pp. 36-50 CrossRef
  8. Buzen, J (1976) Fundamental operational laws of computer system performance. Acta Inform. 14: pp. 167-182 CrossRef
  9. Buzen, J Operational analysis: an alternative to stochastic modeling. In: Ferarri, D eds. (1978) Performance of Computer Installations. North Holland, Amsterdam, pp. 175-194
  10. Cerbone, G, Ricciardi, LM, Sacerdote, L (1981) Mean, variance and the skewness of the first passage time for the Ornstein鈥揢hlenbeck process. Cybern. Syst. 14: pp. 395-429 CrossRef
  11. Choudhury, GL, Whitt, W (1994) Heavy-traffic asymptotic expansions for the asymptotic decay rates in the $$BMAP/G/1$$ B M A P / G / 1 queue. Stoch. Models 10: pp. 453-498 CrossRef
  12. Cohen, JW (1973) Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Probab. 10: pp. 343-353 CrossRef
  13. Cooper, RB (1982) Introduction to Queueing Theory. North Holland, Amsterdam
  14. Cox, DR, Lewis, PAW (1966) The Statistical Analysis of Series of Events. Methuen, London CrossRef
  15. Denning, PJ, Buzen, PJ (1978) The operational analysis of queueing network models. Comput. Surv. 10: pp. 225-261 CrossRef
  16. Dong, J., Whitt, W.: Stationary birth-and-death processes fit to queues with periodic arrival rate functions. In preparation (2014)
  17. Duffield, NG, Whitt, W (1997) Control and recovery from rare congestion events in a large multi-server system. Queueing Syst. 26: pp. 69-104 CrossRef
  18. Eick, SG, Massey, WA, Whitt, W (1993) The physics of the $$M_t/G/\infty $$ M t / G / 鈭queue. Oper. Res. 41: pp. 731-742 CrossRef
  19. El-Taha, M, Stidham, S (1999) Sample-Path Analysis of Queueing Systems. Kluwer, Boston CrossRef
  20. Fendick, KW, Whitt, W (1989) Measurements and approximations to describe the offered traffic and predict the average workload in a single-server queue. Proc. IEEE 71: pp. 171-194 CrossRef
  21. Halfin, S, Whitt, W (1981) Heavy-traffic limits for queues with many exponential servers. Op. Res. 29: pp. 567-588 CrossRef
  22. Hastie, T, Tibshirani, R, Friedman, J (2009) The Elements of Statistical Learning. Springer, New York CrossRef
  23. Iglehart, DL (1965) Limit diffusion approximations for the many-server queue and the repairman problem. J. Appl. Probab. 2: pp. 429-441 CrossRef
  24. Iglehart, DL, Whitt, W (1970) Multiple channel queues in heavy traffic. I. Adv. Appl. Probab. 2: pp. 150-177 CrossRef
  25. Iglehart, DL, Whitt, W (1970) Multiple channel queues in heavy traffic, II: sequences, networks and batches. Adv. Appl. Probab. 2: pp. 355-369 CrossRef
  26. Keiding, N (1975) Maximum likelihood estimation in the birth-and-death process. Ann. Stat. 3: pp. 363-372 CrossRef
  27. Kim, S, Whitt, W (2014) Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes?. Manuf. Serv. Op. Manag. 16: pp. 464-480
  28. Kim, S, Whitt, W (2014) Choosing arrival process models for service systems: tests of a nonhomogeneous Poisson process. Nav. Res. Logist. 17: pp. 307-318
  29. Kristensen, NR, Madsen, H, Jorgensen, SB (2004) Parameter estimation in stochastic grey-box models. Automatica 40: pp. 225-237 CrossRef
  30. Pakes, AG (1975) On the tails of waiting-time distributions. J. Appl. Probab. 12: pp. 555-564 CrossRef
  31. Pang, G, Talreja, R, Whitt, W (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surv. 4: pp. 193-267 CrossRef
  32. Pang, G, Whitt, W (2010) Two-parameter heavy-traffic limits for infinite-server queues. Queueing Syst. 65: pp. 325-364 CrossRef
  33. Pang, G, Whitt, W (2012) The impact of dependent service times on large-scale service systems. Manuf. Serv. Op. Manag. 14: pp. 262-278
  34. Pang, G, Whitt, W (2013) Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Syst. 73: pp. 119-146 CrossRef
  35. Puhalskii, AA, Reiman, MI (2000) The multiclass $$GI/PH/N$$ G I / P H / N queue in the Halfin鈥揥hitt regime. Adv. Appl. Probab. 32: pp. 564-595 CrossRef
  36. Ross, JV, Taimre, T, Pollett, PK (2007) Estimation for queues from queue-length data. Queueing Syst. 55: pp. 131-138 CrossRef
  37. Ross, S.M.: Stochastic Processes, 2nd edn. Wiley, New York (1996)
  38. Sigman, K (1995) Stationary Marked Point Processes: An Intuitive Approach. Chapman and Hall/CRC, New York
  39. Sriram, K, Whitt, W (1986) Characterizing superposition arrival processes in packet multiplexers for voice and data. IEEE J. Sel. Areas Commun. SAC鈥?: pp. 833-846 CrossRef
  40. Stone, CJ (1963) Limit theorems for random walks, birth and death processes and diffusion processes. Ill. J. Math. 4: pp. 638-660
  41. Thomas, MU (1975) Some mean first-passage time approximations for the Ornstein鈥揢hlenbeck process. J. Appl. Probab. 12: pp. 600-604 CrossRef
  42. Vasilakis, C, Marshall, AH (2005) Modelling nationwide hospital length of stay: opening the black box. J. Op. Res. Soc. 56: pp. 862-869 CrossRef
  43. Whitt, W (1981) Comparing counting processes and queues. Adv. Appl. Probab. 13: pp. 207-220 CrossRef
  44. Whitt, W (1982) Approximating a point process by a renewal process: two basic methods. Op. Res. 30: pp. 125-147 CrossRef
  45. Whitt, W (1982) On the heavy-traffic limit theorem for $$GI/G/\infty $$ G I / G / 鈭queue. Adv. Appl. Probab. 14: pp. 171-190 CrossRef
  46. Whitt, W (1983) Untold horrors of the waiting room. What the equilibrium distribution will never tell about the queue-length process. Manag. Sci. 29: pp. 395-408 CrossRef
  47. Whitt, W (1984) Departures from a queue with many busy servers. Math. Op. Res. 9: pp. 534-544 CrossRef
  48. Whitt, W (1989) Planning queueing simulations. Manag. Sci. 35: pp. 1341-1366 CrossRef
  49. Whitt, W (1992) Understanding the efficiency of multi-server service systems. Manag. Sci. 38: pp. 708-723 CrossRef
  50. Whitt, W (2002) Stochastic-Process Limits. Springer, New York
  51. Whitt, W (2004) A diffusion approximation for the $$G/GI/n/m$$ G / G I / n / m queue. Op. Res. 52: pp. 922-941 CrossRef
  52. Whitt, W (2005) Engineering solution of a basic call-center model. Manag. Sci. 51: pp. 221-235 CrossRef
  53. Whitt, W (2006) Staffing a call center with uncertain arrival rate and absenteeism. Prod. Op. Manag. 15: pp. 88-102
  54. Whitt, W (2012) Fitting birth-and-death queueing models to data. Stat. Probab. Lett. 82: pp. 998-1004 CrossRef
  55. Whitt, W (2014) Heavy-traffic limits for queues with periodic arrival rates. Op. Res. Lett. 42: pp. 458-461 CrossRef
  56. Whitt, W (2014) The steady-state distribution of the $$M_t/M/\infty $$ M t / M / 鈭queue with a sinusoidal arrival rate function. Op. Res. Lett. 42: pp. 311-318 CrossRef
  57. Wolff, RW (1965) Problems for statistical inference for birth and death queueing models. Op. Res. 13: pp. 343-357 CrossRef
  58. Wolff, RW The effect of service-time regularity on system performance. In: Chandy, KM, Reiser, M eds. (1977) Comput. Perform.. North-Holland, Amsterdam, pp. 297-304
  59. Yin, L., Uttamchandani, S., Katz, R.: An empirical exploration of black-box performance models for storage systems. In: Proceedings of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, MASCOTS 2006. IEEE, pp. 433鈥?40 (2006)
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Communication Networks
  Probability Theory and Stochastic Processes
  Production and Logistics
  Systems Theory and Control
  
• 出版者：Springer Netherlands
• ISSN：1572-9443

文摘

This paper explores grey-box modeling of queueing systems. A stationary birth-and-death (BD) process model is fitted to a segment of the sample path of the number in the system in the usual way. The birth (death) rates in each state are estimated by the observed number of arrivals (departures) in that state divided by the total time spent in that state. Under minor regularity conditions, if the queue length (number in the system) has a proper limiting steady-state distribution, then the fitted BD process has that same steady-state distribution asymptotically as the sample size increases, even if the actual queue-length process is not nearly a BD process. However, the transient behavior may be very different. We investigate what we can learn about the actual queueing system from the fitted BD process. Here we consider the standard \(GI/GI/s\) queueing model with \(s\) servers, unlimited waiting room and general independent, non-exponential, interarrival-time and service-time distributions. For heavily loaded \(s\) -server models, we find that the long-term transient behavior of the original process, as partially characterized by mean first passage times, can be approximated by a deterministic time transformation of the fitted BD process, exploiting the heavy-traffic characterization of the variability.