Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Inhomogeneous CTMC Birth-and-Death Models Solved by Uniformization with Steady-State Detection

Inhomogeneous CTMC Birth-and-Death Models Solved by Uniformization with Steady-State Detection Time-inhomogeneous queueing models play an important role in service systems modeling. Although the transient solutions of corresponding continuous-time Markov chains (CTMCs) are more precise than methods using stationary approximations, most authors consider their computational costs prohibitive for practical application. This article presents a new variant of the uniformization algorithm that utilizes a modified steady-state detection technique. The presented algorithm is applicable for CTMCs when their stationary solution can be efficiently calculated in advance, particularly for many practically applicable birth-and-death models with limited size. It significantly improves computational efficiency due to an early prediction of an occurrence of a steady state, using the properties of the convergence function of the embedded discrete-time Markov chain. Moreover, in the case of an inhomogeneous CTMC solved in consecutive timesteps, the modification guarantees that the error of the computed probability distribution vector is strictly bounded at each point of the considered time interval. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Modeling and Computer Simulation (TOMACS) Association for Computing Machinery

Inhomogeneous CTMC Birth-and-Death Models Solved by Uniformization with Steady-State Detection

Download PDF
18 pages

Loading next page...
 
/lp/association-for-computing-machinery/inhomogeneous-ctmc-birth-and-death-models-solved-by-uniformization-1ZylQXfrCx
Publisher
Association for Computing Machinery
Copyright
Copyright © 2020 ACM
ISSN
1049-3301
eISSN
1558-1195
DOI
10.1145/3373758
Publisher site
See Article on Publisher Site

Abstract

Time-inhomogeneous queueing models play an important role in service systems modeling. Although the transient solutions of corresponding continuous-time Markov chains (CTMCs) are more precise than methods using stationary approximations, most authors consider their computational costs prohibitive for practical application. This article presents a new variant of the uniformization algorithm that utilizes a modified steady-state detection technique. The presented algorithm is applicable for CTMCs when their stationary solution can be efficiently calculated in advance, particularly for many practically applicable birth-and-death models with limited size. It significantly improves computational efficiency due to an early prediction of an occurrence of a steady state, using the properties of the convergence function of the embedded discrete-time Markov chain. Moreover, in the case of an inhomogeneous CTMC solved in consecutive timesteps, the modification guarantees that the error of the computed probability distribution vector is strictly bounded at each point of the considered time interval.

Journal

ACM Transactions on Modeling and Computer Simulation (TOMACS) – Association for Computing Machinery

Published: May 31, 2020

Keywords: Uniformization

References

  • The modern call-center: A multi-disciplinary perspective on operations management research
    Aksin, Zeynep; Armony, Mor; Mehrotra, Vijay
  • On-the-fly uniformization of time-inhomogeneous infinite Markov population models
    Andreychenko, leksandr; Crouzen, Pepijn; Mikeev, Linar; Wolf, Verena
  • On the numerical analysis of inhomogeneous continuous-time Markov chains
    Arns, Markus; Buchholz, Peter; Panchenko, Andriy
  • Queueing Networks and Markov Chains
    Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S.
  • On the M(n)/M(n)/s queue with impatient calls
    Brandt, Andreas; Brandt, Manfred
  • Asymptotic results and a Markovian approximation for the M(n)/M(n)/s+GI system
    Brandt, Andreas; Brandt, Manfred
  • Statistical analysis of a telephone call center
    Brown, Lawrence; Gans, Noah; Mandelbaum, Avishai; Sakov, Anat; Shen, Haipeng; Zeltyn, Sergey; Zhao, Linda
  • Inhomogeneous CTMC model of a call center with balking and abandonment
    Burak, Maciej Rafał
  • Computing discrete poisson probabilities for uniformization algorithm
    Burak, Maciej Rafał
  • Staffing multiskill call centers via linear programming and simulation
    Cezik, Mehmet Tolga; L’Ecuyer, Pierre
  • G-RAND: A phase-type approximation for the nonstationary queue
    Creemers, Stefan; Defraeye, Mieke; Van Nieuwenhuyse, Inneke
  • Staffing and scheduling under nonstationary demand for service: A literature review
    Defraeye, Mieke; Van Nieuwenhuyse, Inneke
  • Markov chain models of a telephone call center with call blending
    Deslauriers, Alexandre; L’Ecuyer, Pierre; Pichitlamken, Juta; Ingolfsson, Armann; Avramidis, Athanassios N.
  • Stochastic grey-box modeling of queueing systems: Fitting birth-and-death processes to data
    Dong, James; Whitt, Ward
  • Staffing of time-varying queues to achieve time-stable performance
    Feldman, Zohar; Mandelbaum, Avishai; Massey, William A.; Whitt, Ward
  • Telephone call centers: Tutorial, review, and research prospects
    Gans, Noah; Koole, Ger; Mandelbaum, Avishai
  • Transient solutions in Markovian queueing systems
    Grassmann, Winfried K.
  • Some effects of nonstationarity on multiserver Markovian queueing systems
    Green, Linda; Kolesar, Peter; Svoronos, Anthony
  • Improving the SIPP approach for staffing service systems that have cyclic demands
    Green, Linda V.; Kolesar, Peter J.; Soares, João
  • An improved heuristic for staffing telephone call centers with limited operating hours
    Green, Linda V.; Kolesar, Peter J.; Soares, João
  • Coping with time-varying demand when setting staffing requirements for a service system
    Green, Linda V.; Kolesar, Peter J.; Whitt, Ward
  • The randomization technique as a modeling tool and solution procedure for transient Markov processes
    Gross, Donald; Miller, Douglas R.
  • Dynamic Contact Centers with Impatient Customers and Retrials
    Henken, Kirsten
  • A survey and experimental comparison of service-level-approximation methods for nonstationary M(t)/M/s(t) queueing systems with exhaustive discipline
    Ingolfsson, Armann; Akhmetshina, Elvira; Budge, Susan; Li, Yongyue; Wu, Xudong
  • Combining integer programming and the randomization method to schedule employees
    Ingolfsson, Armann; Campello, Fernanda; Wu, Xudong; Cabral, Edgar
  • Efficient and reliable computation of birth-death process performance measures
    Ingolfsson, Armann; Tang, Ling
  • Performance indicators for call centers with impatient customers
    Jouini, Oualid; Koole, Ger; Roubos, Alex
  • Safe on-the-fly steady-state detection for time-bounded reachability
    Katoen, Joost-Pieter; Zapreev, Ivan S.
  • Statistical analysis with Little’s law
    Kim, Song-Hee; Whitt, Ward
  • Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes?Manufacturing 8 Service Operations Management 16, 3 (July 2014), 464--480
    Kim, Song-Hee; Whitt, Ward
  • Choosing arrival process models for service systems: Tests of a nonhomogeneous poisson process
    Kim, Song-Hee; Whitt, Ward
  • Stiffness-tolerant methods for transient analysis of stiff Markov chains
    Malhotra, Manish; Muppala, Jogesh K.; Trivedi, Kishor S.
  • Data-stories about (im)patient customers in tele-queues
    Mandelbaum, Avishai; Zeltyn, Sergey
  • On queueing with customer impatience until the beginning of service
    Movaghar, Ali
  • Numerical transient solution of finite Markovian queueing systems
    Muppala, Jogesh K.; Trivedi, Kishor S.
  • Estimating the largest eigenvalue of a positive definite matrix
    O’Leary, Dianne P.; Stewart, G. W.; Vandergraft, James S.
  • Numerical transient analysis of Markov models
    Reibman, Andrew; Trivedi, Kishor
  • Exact methods for the transient analysis of nonhomogeneous continuous time Markov chains
    Rindos, Andy; Woolet, Steven; Viniotis, Ioannis; Trivedi, Kishor
  • Performance analysis of time-dependent queueing systems: Survey and classification
    Schwarz, Justus Arne; Selinka, Gregor; Stolletz, Raik
  • Introduction to the Numerical Solution of Markov Chains
    Stewart, William J.
  • Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling
    Stewart, William J.
  • Uniformization for nonhomogeneous Markov chains
    van Dijk, Nico M.
  • Transient solution of Markov models by combining adaptive and standard uniformization
    Van Moorsel, Aad P. A.; Sanders, William H.
  • Numerical solution of non-homogeneous markov processes through uniformization
    Van Moorsel, Aad P. A.; Wolter, Katinka
  • Das Gesetz der kleinen Zahlen
    von Bortkiewicz, Ladislaus
  • Engineering solution of a basic call-center model
    Whitt, Ward
  • Fitting birth-and-death queueing models to data
    Whitt, Ward
  • Numerical vs
    Younes, Håkan L. S.; Kwiatkowska, Marta; Norman, Gethin; Parker, David