An exact root-free method for the expected queue length for a class of discrete-time queueing systems

Anna Oblakova, Ahmad Al Hanbali, Richard Boucherie, Jan C.W. van Ommeren, Henk Zijm

Research output: Contribution to journalArticleAcademicpeer-review

6 Downloads (Pure)

Abstract

For a class of discrete-time queueing systems, we present a new exact method of computing both the expectation and the distribution of the queue length. This class of systems includes the bulk-service queue and the fixed-cycle traffic-light (FCTL) queue, which is a basic model in traffic-control research and can be seen as a non-exhaustive time-limited polling system. Our method avoids finding the roots of the characteristic equation, which enhances both the reliability and the speed of the computations compared to the classical root-finding approach. We represent the queue-length expectation in an exact closed-form expression using a contour integral. We also introduce several realistic modifications of the FCTL model. For the FCTL model for a turning flow, we prove a decomposition result. This allows us to derive a bound on the difference between the bulk-service and FCTL expected queue lengths, which turns out to be small in most of the realistic cases.
Original languageEnglish
Pages (from-to)257-292
Number of pages36
JournalQueueing systems
Volume92
Issue number3-4
Early online date17 May 2019
DOIs
Publication statusPublished - 1 Aug 2019

Fingerprint

Expected Length
Queue Length
Queueing System
Discrete-time Systems
Telecommunication traffic
Traffic
Roots
Cycle
Queue
Polling Systems
Contour integral
Root-finding
Traffic Control
Exact Method
Traffic control
Characteristic equation
Closed-form
Model
Decomposition
Decompose

Keywords

  • UT-Hybrid-D
  • Fixed-cycle traffic-light model
  • Roots
  • Contour integrals
  • Bulk-service queue

Cite this

@article{738cf9a32aef4aa0ad818b996d46159d,
title = "An exact root-free method for the expected queue length for a class of discrete-time queueing systems",
abstract = "For a class of discrete-time queueing systems, we present a new exact method of computing both the expectation and the distribution of the queue length. This class of systems includes the bulk-service queue and the fixed-cycle traffic-light (FCTL) queue, which is a basic model in traffic-control research and can be seen as a non-exhaustive time-limited polling system. Our method avoids finding the roots of the characteristic equation, which enhances both the reliability and the speed of the computations compared to the classical root-finding approach. We represent the queue-length expectation in an exact closed-form expression using a contour integral. We also introduce several realistic modifications of the FCTL model. For the FCTL model for a turning flow, we prove a decomposition result. This allows us to derive a bound on the difference between the bulk-service and FCTL expected queue lengths, which turns out to be small in most of the realistic cases.",
keywords = "UT-Hybrid-D, Fixed-cycle traffic-light model, Roots, Contour integrals, Bulk-service queue",
author = "Anna Oblakova and {Al Hanbali}, Ahmad and Richard Boucherie and {van Ommeren}, {Jan C.W.} and Henk Zijm",
note = "Springer deal",
year = "2019",
month = "8",
day = "1",
doi = "10.1007/s11134-019-09614-1",
language = "English",
volume = "92",
pages = "257--292",
journal = "Queueing systems",
issn = "0257-0130",
publisher = "Springer",
number = "3-4",

}

An exact root-free method for the expected queue length for a class of discrete-time queueing systems. / Oblakova, Anna ; Al Hanbali, Ahmad ; Boucherie, Richard; van Ommeren, Jan C.W.; Zijm, Henk.

In: Queueing systems, Vol. 92, No. 3-4, 01.08.2019, p. 257-292.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - An exact root-free method for the expected queue length for a class of discrete-time queueing systems

AU - Oblakova, Anna

AU - Al Hanbali, Ahmad

AU - Boucherie, Richard

AU - van Ommeren, Jan C.W.

AU - Zijm, Henk

N1 - Springer deal

PY - 2019/8/1

Y1 - 2019/8/1

N2 - For a class of discrete-time queueing systems, we present a new exact method of computing both the expectation and the distribution of the queue length. This class of systems includes the bulk-service queue and the fixed-cycle traffic-light (FCTL) queue, which is a basic model in traffic-control research and can be seen as a non-exhaustive time-limited polling system. Our method avoids finding the roots of the characteristic equation, which enhances both the reliability and the speed of the computations compared to the classical root-finding approach. We represent the queue-length expectation in an exact closed-form expression using a contour integral. We also introduce several realistic modifications of the FCTL model. For the FCTL model for a turning flow, we prove a decomposition result. This allows us to derive a bound on the difference between the bulk-service and FCTL expected queue lengths, which turns out to be small in most of the realistic cases.

AB - For a class of discrete-time queueing systems, we present a new exact method of computing both the expectation and the distribution of the queue length. This class of systems includes the bulk-service queue and the fixed-cycle traffic-light (FCTL) queue, which is a basic model in traffic-control research and can be seen as a non-exhaustive time-limited polling system. Our method avoids finding the roots of the characteristic equation, which enhances both the reliability and the speed of the computations compared to the classical root-finding approach. We represent the queue-length expectation in an exact closed-form expression using a contour integral. We also introduce several realistic modifications of the FCTL model. For the FCTL model for a turning flow, we prove a decomposition result. This allows us to derive a bound on the difference between the bulk-service and FCTL expected queue lengths, which turns out to be small in most of the realistic cases.

KW - UT-Hybrid-D

KW - Fixed-cycle traffic-light model

KW - Roots

KW - Contour integrals

KW - Bulk-service queue

U2 - 10.1007/s11134-019-09614-1

DO - 10.1007/s11134-019-09614-1

M3 - Article

VL - 92

SP - 257

EP - 292

JO - Queueing systems

JF - Queueing systems

SN - 0257-0130

IS - 3-4

ER -