A Diffusion Model Approximation for the GI/G/1 Queue in Heavy Traffic

We consider a single-server queuing system where the interarrival times are independent and identically distributed (i.i.d.) random variables, customers are served in order of arrival, the service times of the various customers are i.i.d. random variables, and the interarrival and service times form independent sequences. Lindley1 obtained a recursive equation for the delay-time of the nth arriving customer, an integral equation for the delay time of a customer in the steady-state, and conditions for the latter to have a nondegenerate limit. Lindley's equations have not yielded to conveniently used analytical solutions, except in some special cases, stimulating a search for approximations to the distributions of general interest. In this paper, we approximate the queue length and delay processes by appropriately chosen diffusion processes. This method of approximation appears to have been introduced by Gaver2 and Newell.3 Gaver and Newell considered the M/G/I queue; we extend their approximate models to the G I / G / I queue. Other methods for obtaining diffusion approximations for queuing processes involve applying the theory of weak convergence to sequences of approximating processes. Whitt 4 is a survey of these methods and contains an extensive bibliography. We show that the diffusion models developed in this paper agree with the limiting processes obtained by weak convergence methods. Important features of this paper are the use of the M/M/ L queue to motivate a diffusion process approximation for the single-server queue and the use of elementary renewal theory results to obtain the param1637