RESEARCH STATEMENT
DYNAMIC SCHEDULING IN QUEUEING NETWORKS
STEVEN L. BELL
INTRODUCTION
Queueing Networks are widely used to model communication, computer, and manufacturing systems. One of the main issues in operating such systems is how to efficiently allocate scarce resources to improve performance. For example, a communication network needs to provide a guaranteed amount of bandwidth for a real-time video application to ensure that the transmitted image is void of jitter, while simultaneously minimizing congestion for other applications subject to available bandwidth. A computer chip manufacturer faces similar constraints when attempting to streamline the production process to maximize profit. In queueing models, two control mechanisms are of particular importance: routing and sequencing. A routing policy determines which route a particular job takes through the network, whereas a sequencing policy specifies which job class to serve next at each station. (In the first example above, a natural class division might be real-time versus non-real-time traffic.) Due to the randomness of the arrival streams and the service times, it may be desirable to allow policies that are dynamically adjustable to achieve maximum efficiency. Policies that continuously adapt to the state of the system, so-called continuous review policies, are of special interest and are the main focus of what follows.
BROWNIAN CONTROL PROBLEMS Dynamic scheduling problems for queueing networks are notoriously difficult and can in many cases be shown to be computationally intractable even for very simple network topologies [5]. (These difficulties arise especially in multi-class queueing networks like those mentioned above.) As an alternative to a direct approach, various authors have proposed so-called Brownian control problems as formal heavy traffic approximations for such scheduling problems. (The heavy traffic assumption is justified by the empirical fact that ``the important features of good control policies are displayed in sharpest relief" [2] in heavily loaded networks.) These Brownian network models take queue lengths to be continuous rather than discrete and postulate the approximation of network control problems by control problems involving Brownian motions. For some networks, the associated Brownian control problems have been solved (cf. e.g. [2] and [4]), and their solutions have been cleverly interpreted to produce candidates for optimal policies in the original networks. Although these policies have performed well when simulated, there are few rigorous proofs of the asymptotic optimality of these policies. Moreover, the derivations of the proposed optimal policies have usually been ad hoc. My research is aimed at establishing asymptotic optimality of such policies for certain dynamic scheduling problems. The problem on which I am currently working is described below.
A PARALLEL SERVER PROBLEM
Consider the problem of assigning jobs to a collection of CPUs working in parallel. Jobs of various classes arrive at random and each job requires service at one of the processors. (Some processors may be specialized and only able to handle certain classes of jobs.) The amount of work, measured in units of required processing time, that each job brings to the system depends (stochastically) on its class as well as on the particular processor to which it is assigned. For concreteness, assume job assignment is made when a job is about to be processed. After service is completed, the job leaves the system. In addition, there is a class dependent, per-unit-time holding cost associated with each job in the system. The system manager seeks to minimize total cost by dynamically assigning waiting jobs to available processors. (This model is also known in the literature as call center.) One may view such an assignment plan as a hybrid of the aforementioned routing and sequencing policies. Except under very special circumstances, the assignment problem cannot be solved explicitly.
ASYMPTOTIC OPTIMALITY
As a step towards obtaining an asymptotically optimal solution to the assignment problem described above, [1] considers a parallel server problem with two job classes and two processors in heavy traffic. Each job class is queued up in a separate buffer and served in a first-in-first-out (FIFO) fashion by the two processors subject to the following restrictions. Class 1 jobs may be (dynamically) assigned to either processor, whereas class 2 jobs are permanently assigned to processor 2. The candidate optimal continuous review policy is the following: both processors work on class 1 jobs when the total number of class 1 jobs in the system exceeds a certain threshold. At all other times, class 1 jobs are exclusively assigned to processor 1, and each processor attends to its own designated job class whenever possible. This policy exploits the overlapping capabilities of the processors to produce a one-dimensional limiting Brownian motion, i.e., the limiting Brownian network behaves as if the two processors pool to form a single ``super-processor''. This phenomenon has been named resource pooling in the literature and is a special case of a more general phenomenon called state space collapse. It is shown in [1] that the threshold policy is asymptotically optimal (in the heavy traffic limit) in the sense that it minimizes normalized discounted cost over the infinite horizon. Work in progress is aimed at extending this analysis to the general assignment problem under a complete resource pooling condition identified by Harrison and Lopez [4].
REFERENCES
[1] S.L. Bell and R.J. Williams. Dynamic scheduling of a system with two parallel servers: asymptotic optimality of a threshold policy in heavy traffic. In preparation.
[2] F.P. Kelly and C.N. Laws. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems, 13:47-86, 1993.
[3] J.M. Harrison and M.J. López. Heavy traffic resource pooling in parallel-server systems. Preprint, 1998.
[4] J.M. Harrison and L.M. Wein. Scheduling networks of queues: heavy traffic analysis of a simple open network. Queueing Systems, 5:265-280, 1989.
[5] C.H. Papadimitriou and J.N. Tsitsiklis.
The complexity of optimal queueing network control.
To appear in Math. Op. Res.