Applying optimization theory to study extremal GI/GI/1 transient mean waiting times

Yan Chen () and Ward Whitt ()
Additional contact information
Yan Chen: Columbia University
Ward Whitt: Columbia University

Queueing Systems: Theory and Applications, 2022, vol. 101, issue 3, No 1, 197-220

Abstract: Abstract We study the tight upper bound of the transient mean waiting time in the classical GI/GI/1 queue over candidate interarrival-time distributions with finite support, given the first two moments of the interarrival time and the full service-time distribution. We formulate the problem as a non-convex nonlinear program. We derive the gradient of the transient mean waiting time and then show that a stationary point of the optimization can be characterized by a linear program. We develop and apply a stochastic variant of the Frank and Wolfe (Naval Res Logist Q 3:95–110, 1956) algorithm to find a stationary point for any given service-time distribution. We also establish necessary conditions and sufficient conditions for stationary points to be three-point distributions or special two-point distributions. We illustrate by applying simulation together with optimization to analyze several examples.

Keywords: GI/GI/1 queue; Tight bounds; Extremal queues; Bounds for the transient mean waiting time; Moment problem; Primary 60K25; Secondary 65C50; 90B22 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-021-09725-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:queues:v:101:y:2022:i:3:d:10.1007_s11134-021-09725-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-021-09725-8

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().