Introduction to Matrix-Analytic Methods in Queues 2

1Single-Server Queues Embedded at Departure Epochs

Wherever we go and whatever we do, we invariably have to wait for our turn to get service or attention or execute our job. When we look at the total time spent in executing the job, it includes the actual time for executing the job plus the waiting time (the time spent before our job gets into service). The study of such waiting line problems both from the customers’ and the service facilities’ points of view, so as to optimize the time in the system and to best utilize the resources, falls under the general topic of queueing models.

Queueing theory plays an important role in many areas, notably telecommunications, production and manufacturing engineering, computer science and other service offering facilities. Queueing theory was developed originally in the context of telephone traffic congestion by Danish Mathematician A.K. Erlang in 1909. He noticed that the telephone systems were generally characterized by either Poisson input and exponential holding times and multiple channels or by Poisson input and constant holding times and a single channel. Erlang was responsible for the concept of stationary equilibrium. E.C. Molina, in 1927, published Applications of the Theory of Probability to Telephone Trunking Problems. In the early 1930s, F. Pollaczek did some fundamental work on Poisson input, arbitrary output and single/multiple channel problems. At the same time, A. Kolmogorov and A. Khintchine (from Russia), C.D. Crommelin ...