LENGTH DISTRIBUTIONS AND DYNAMIC BUFFER SIZING IN MULTI-SERVER QUEUEING SYSTEMS

Multi-server queueing models are common in several areas of operations research, including manufacturing systems, call centers, and computer networks. Many researchers have studied analytic approximations for multi-server... [ view full abstract ]

Multi-server queueing models are common in several areas of operations research, including manufacturing systems, call centers, and computer networks. Many researchers have studied analytic approximations for multi-server queueing systems, particularly the estimation of average waiting times in systems with non-exponential service distributions. However, simulation still remains the preferred technique for many problems involving multi-server queues,including problems of resource allocation in systems with finite
storage buffers.

This talk presents new analytic approximation techniques for the queue length distributions in M/G/1 and M/G/c queues. The derivations are based on the fundamental laws of queuing systems and require only the first two moments of the service time distribution. Comparisons to simulation estimates show that both approximations are accurate for a range of practical systems, including those with high utilizations and high service time variability.

Multiple authors have used Little's Result to derive a relationship between the queue length and residual service times. We first adapt these results
to derive a two-moment approximation formula for the M/G/1 queue length distribution. This result has several desirable properties: it requires only the mean and variance of the service time distribution rather than the complete moment-generating function, it is exact for M/M/1 systems, and it can be used to recover the exact mean queue length.

Extending the single-server approximation to multi-server systems, we observe that, from the perspective of a customer waiting in line, waiting in an M/G/c queue is like waiting in an M/G/1 queue with service rate multiplied by a factor of c. Therefore, it is possible to derive an expression for the queue length in a multi-server system that has a form similar to the single-server approximation. Simulation experiments show that this approach is accurate for many practical systems, including queues with dozens of servers and high service time variability.

The conclusion of the talk features a presentation of new research in progress on dynamic buffer-resizing in systems of multi-server queues. Many systems are constrained by a limited amount of storage that must be shared among a series of production centers. For example, in a job shop, there may be a limited amount of buffer space for work-in-progress that must be allocated among different production lines. Therefore, efficient techniques for reallocating buffer space in response to changes in load are of both practical and theoretical interest.

The key result of this section is the use of the multi-server queue length approximation to estimate the blocking probability for M/G/c/b queues, drawing on heuristics developed by Tijms. We will also discuss potential applications and open problems related to analytic buffer sizing models.