Approximations for the Queue Length Distributions of Time-Varying Many-Server Queues

Jamol Pender () and Young Myoung Ko ()
Additional contact information
Jamol Pender: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Young Myoung Ko: Department of Industrial and Management Engineering, Pohang University of Science and Technology, Pohang, Gyeongbuk, 37673, Korea

INFORMS Journal on Computing, 2017, vol. 29, issue 4, 688-704

Abstract: This paper presents a novel and computationally efficient methodology for approximating the queue length (the number of customers in the system) distributions of time-varying non-Markovian many-server queues (e.g., G t / G t / n t queues), where the number of servers ( n t ) is large. Our methodology consists of two steps. The first step uses phase-type distributions to approximate the general interarrival and service times, thus generating an approximating Ph t / Ph t / n t queue. The second step develops strong approximation theory to approximate the Ph t / Ph t / n t queue with fluid and diffusion limits whose mean and variance can be computed using ordinary differential equations. However, by naively representing the Ph t / Ph t / n t queue as a Markov process by expanding the state space, we encounter the lingering phenomenon even when the queue is overloaded . Lingering typically occurs when the mean queue length is equal or near the number of servers, however, in this case it also happens when the queue is overloaded and this time is not of zero measure. As a result, we develop an alternative representation for the queue length process that avoids the lingering problem in the overloaded case, thus allowing for the derivation of a Gaussian diffusion limit. Finally, we compare the effectiveness of our proposed method with discrete event simulation in a variety parameter settings and show that our approximations are very accurate.

Keywords: time-varying non-Markovian queues; many-server queues; fluid and diffusion limits; strong approximations (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0760 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:4:p:688-704

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().