Transform-Free Analysis of M/G/1/K and Related Queues

Abstract

Using constructive, sample-path arguments, we derive a variety of transform-free results about queue lengths and waiting times for the M/G/1/K queue. In classical analyses of M/G/1/K, it is typical to work with Markov processes obtained by defining the “state” of the system at a time epoch to be the number of customers present and, as supplementary information, the remaining service time of the customer, if any, in service. In contrast, the key idea behind our analysis is to work with a modified Markov process that has a more-detailed state description. At any time epoch t when the server is busy, we replace “the number of customers present” by two variables, namely (a) the number of customers who where (and still are) waiting in the queue immediately after the start of the service in progress, and (b) the number of customers who arrived during that same service but prior to t. We show that this minor change of state definition, coupled with a rigorous formalization of the intuitive notion of a “test customer” (whose viewpoint is adopted in our analysis of the modified Markov process) makes possible a surprisingly simple analysis of the M/G/1/K queue. We also show that our method can be extended easily to yield similar results for various generalizations of the basic M/G/1/K model.

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 — 17 citations exist upstream.

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