On dynamic scheduling of a parallel server system with complete resource pooling

R. J. Williams
ABSTRACT
This paper considers a dynamic scheduling problem for a parallel server queueing system. This system might be viewed as a model for a manufacturing or computer system, consisting of a bank of buffers for holding incoming jobs and a bank of servers for processing these jobs. Incoming jobs are classified into one of several different classes (or buffers). Jobs within a class are served on a first-in-first-out basis by one of a bank of parallel servers. Servers may have differing but overlapping capabilities and so may be able to service more than one class. The system manager seeks to minimize holding costs by dynamically allocating waiting jobs to available servers.

With the exception of a few special cases, the dynamic scheduling problem for this system cannot be analyzed exactly and it is natural to consider more tractable approximations. One class of such approximations are the so-called Brownian control problems, first introduced by Harrison. These are formal heavy traffic approximations to queueing control problems. Various authors have used analysis of these Brownian control problems, together with clever interpretation of their optimal (analytic) solutions to suggest ``good" policies for the original queueing control problems.

For the parallel server system considered here, in a recent work, Harrison and Lopez studied the associated Brownian control problem and identified a condition under which the solution of that problem exhibits complete resource pooling, i.e., in the Brownian model, the efforts of the individual servers can be efficiently combined to act as a single pooled resource or "superserver". Under this condition, Harrison and Lopez conjecture that a "discrete review" scheduling policy (for the original parallel server system), obtained by using the BIGSTEP discretization procedure of Harrison, is asymptotically optimal in the heavy traffic limit.

In this paper, focussing on the parameter regime associated with the complete resource pooling condition of Harrison and Lopez, we first review the formulation and solution of the Brownian control problem, and then we propose an alternative to the Harrison-Lopez discrete-review policy, namely, a simple dynamic threshold-type scheduling policy, which we conjecture is asymptotically optimal in the heavy traffic limit. Although our review of the Brownian control problem has many elements in common with the treatment in Harrison and Lopez and it certainly draws on the results proved there, our presentation differs from in several respects. In particular, we have attempted to distill (and expand where necessary) results from prior works. In addition, our proposal for a dynamic threshold-type policy, especially the server-buffer tree introduced here, are new. To support our conjecture that the proposed threshold policy is asymptotically optimal, we note that a proof of this for a two-server system is given in Bell-Williams. Work in progress is directed to extending this to the many server case.

This paper appears in "Analysis of Communication Networks: Call Centres, Traffic and Performance", D. R. McDonald and S. R. E. Turner (eds.), Fields Institute Communications Volume 28, American Mathematical Society, 2000.
For a copy of a preprint for personal, scientific, non commercial use, click here for postscript and here for pdf.