Heavy-traffic analysis through uniform acceleration of queues with diminishing populations

Gianmarco Bet (Corresponding author), Remco van der Hofstad, Johan S.H. van Leeuwaarden

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We consider a single-server queue that serves a finite population of n customers that will enter the queue (require service) only once, also known as the Δ(i)/G/1 queue. This paper presents a method for analyzing heavy-traffic behavior by using uniform acceleration, which simultaneously lets n and the service rate grow large, while the initial resource utilization approaches one. A key feature of the model is that, as time progresses, more customers have joined the queue, and fewer customers can potentially join. This diminishing population gives rise to a class of reflected stochastic processes that vanish over time and hence do not have a stationary distribution. We establish that, when the arrival times are exponentially distributed, by suitably rescaling space and time, the queue-length process converges to a Brownian motion with a negative quadratic drift, a stochastic-process limit that captures the effect of the diminishing population. When the arrival times are generally distributed, our techniques provide information on the typical queue length and the first busy period.

Original languageEnglish
Pages (from-to)821-864
Number of pages44
JournalMathematics of Operations Research
Volume44
Issue number3
DOIs
Publication statusPublished - Aug 2019

Fingerprint

Traffic Analysis
Heavy Traffic
Diminishing
Random processes
Queue
Customers
Arrival Time
Queue Length
Stochastic Processes
Brownian movement
Single Server Queue
Busy Period
Servers
Finite Population
Rescaling
Stationary Distribution
Join
Brownian motion
Vanish
Converge

Keywords

  • Asymptotic analysis
  • Continuous-mapping approach
  • Heavy-traffic approximations
  • Martingale functional CLT
  • Queueing theory
  • Transitory queueing systems
  • Uniform acceleration technique
  • queueing theory
  • uniform acceleration technique
  • asymptotic analysis
  • martingale functional CLT
  • continuous-mapping approach
  • transitory queueing systems
  • heavy-traffic approximations

Cite this

@article{8f38229806184f9b8a7f2d9727141f83,
title = "Heavy-traffic analysis through uniform acceleration of queues with diminishing populations",
abstract = "We consider a single-server queue that serves a finite population of n customers that will enter the queue (require service) only once, also known as the Δ(i)/G/1 queue. This paper presents a method for analyzing heavy-traffic behavior by using uniform acceleration, which simultaneously lets n and the service rate grow large, while the initial resource utilization approaches one. A key feature of the model is that, as time progresses, more customers have joined the queue, and fewer customers can potentially join. This diminishing population gives rise to a class of reflected stochastic processes that vanish over time and hence do not have a stationary distribution. We establish that, when the arrival times are exponentially distributed, by suitably rescaling space and time, the queue-length process converges to a Brownian motion with a negative quadratic drift, a stochastic-process limit that captures the effect of the diminishing population. When the arrival times are generally distributed, our techniques provide information on the typical queue length and the first busy period.",
keywords = "Asymptotic analysis, Continuous-mapping approach, Heavy-traffic approximations, Martingale functional CLT, Queueing theory, Transitory queueing systems, Uniform acceleration technique, queueing theory, uniform acceleration technique, asymptotic analysis, martingale functional CLT, continuous-mapping approach, transitory queueing systems, heavy-traffic approximations",
author = "Gianmarco Bet and {van der Hofstad}, Remco and {van Leeuwaarden}, {Johan S.H.}",
year = "2019",
month = "8",
doi = "10.1287/moor.2018.0947",
language = "English",
volume = "44",
pages = "821--864",
journal = "Mathematics of Operations Research",
issn = "0364-765X",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "3",

}

Heavy-traffic analysis through uniform acceleration of queues with diminishing populations. / Bet, Gianmarco (Corresponding author); van der Hofstad, Remco; van Leeuwaarden, Johan S.H.

In: Mathematics of Operations Research, Vol. 44, No. 3, 08.2019, p. 821-864.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Heavy-traffic analysis through uniform acceleration of queues with diminishing populations

AU - Bet, Gianmarco

AU - van der Hofstad, Remco

AU - van Leeuwaarden, Johan S.H.

PY - 2019/8

Y1 - 2019/8

N2 - We consider a single-server queue that serves a finite population of n customers that will enter the queue (require service) only once, also known as the Δ(i)/G/1 queue. This paper presents a method for analyzing heavy-traffic behavior by using uniform acceleration, which simultaneously lets n and the service rate grow large, while the initial resource utilization approaches one. A key feature of the model is that, as time progresses, more customers have joined the queue, and fewer customers can potentially join. This diminishing population gives rise to a class of reflected stochastic processes that vanish over time and hence do not have a stationary distribution. We establish that, when the arrival times are exponentially distributed, by suitably rescaling space and time, the queue-length process converges to a Brownian motion with a negative quadratic drift, a stochastic-process limit that captures the effect of the diminishing population. When the arrival times are generally distributed, our techniques provide information on the typical queue length and the first busy period.

AB - We consider a single-server queue that serves a finite population of n customers that will enter the queue (require service) only once, also known as the Δ(i)/G/1 queue. This paper presents a method for analyzing heavy-traffic behavior by using uniform acceleration, which simultaneously lets n and the service rate grow large, while the initial resource utilization approaches one. A key feature of the model is that, as time progresses, more customers have joined the queue, and fewer customers can potentially join. This diminishing population gives rise to a class of reflected stochastic processes that vanish over time and hence do not have a stationary distribution. We establish that, when the arrival times are exponentially distributed, by suitably rescaling space and time, the queue-length process converges to a Brownian motion with a negative quadratic drift, a stochastic-process limit that captures the effect of the diminishing population. When the arrival times are generally distributed, our techniques provide information on the typical queue length and the first busy period.

KW - Asymptotic analysis

KW - Continuous-mapping approach

KW - Heavy-traffic approximations

KW - Martingale functional CLT

KW - Queueing theory

KW - Transitory queueing systems

KW - Uniform acceleration technique

KW - queueing theory

KW - uniform acceleration technique

KW - asymptotic analysis

KW - martingale functional CLT

KW - continuous-mapping approach

KW - transitory queueing systems

KW - heavy-traffic approximations

UR - http://www.scopus.com/inward/record.url?scp=85071880695&partnerID=8YFLogxK

U2 - 10.1287/moor.2018.0947

DO - 10.1287/moor.2018.0947

M3 - Article

AN - SCOPUS:85071880695

VL - 44

SP - 821

EP - 864

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 3

ER -