Transform-Free Analysis of M/G/1/K and Related Queues
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 were (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 several generalizations of the basic M/G/1/K
model.