Simple Inequalities for the D/G/1 Queue

Abstract

During the last quarter century a large number of papers, starting in 1962 with J. F. C. Kingman, have been written about inequalities for queues. Their objective has been to eliminate the need for detailed distributional analysis by providing upper and lower bounds for such entities as the expected waiting time and the probability of no waiting. Notable results include Kingman's upper bound for the expected waiting time in a GI/G/1 queue and K. T. Marshall's lower bound for the expected waiting time in a D/G/1 queue. In this paper we present a new method for obtaining bounds for the stationary D/G/1 queue. The basic idea is to translate crude bounds on the probability that the system is empty at time t into sharp bounds for the expected waiting time. The crudest possible bounds on the probability that the system is empty at time t reproduce the Kingman upper bound and the Marshall lower bound, and show that the Marshall lower bound is tight for the D/G/1 queue and is attained if and only if the service times are integer (random) multiples of the interarrival time.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 13 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.