Queueing Systems 33 (1999) 339–368 339Heavy traffic resource pooling in parallel-server systemsJ. Michael Harrisonaand Marcel J. L´opezbaGraduate School of Business, Stanford University, Stanford, CA 94305, USAE-mail: [email protected] School of International Relations and Pacific Studies, University of California, San Diego,La Jolla, CA 92093-0519, USAE-mail: [email protected] 26 January 1999; revised 22 April 1999We consider a queueing system with r non-identical servers working in parallel, exoge-nous arrivals into m different job classes, and linear holding costs for each class. Eacharrival requires a single service, which may be provided by any of several different serversin our general formulation; the service time distribution depends on both the job class beingprocessed and the server selected. The system manager seeks to minimize holding costsby dynamically scheduling waiting jobs onto available servers. A linear program involvingonly first-moment data (average arrival rates and mean service times) is used to define heavytraffic for a system of this form, and also to articulate a condition of overlapping servercapabilities which leads to resource pooling in the heavy traffic limit. Assuming that thelatter condition holds, we rescale time and state space in standard fashion, then identifya Brownian control problem that is the formal heavy traffic limit of our rescaled schedul-ing problem. Because of the assumed overlap in server capabilities, the limiting Browniancontrol problem is effectively one-dimensional, and it admits a pathwise optimal solution.That is, in the limiting Brownian control problem the multiple servers of our original modelmerge to form a single pool of service capacity, and there exists a dynamic control policywhich minimizes cumulative cost incurred up to any time t with probability one. Interpretedin our original problem context, the Brownian solution suggests the following: virtually allbacklogged work should be held in one particular job class, and all servers can and shouldbe productively employed except when the total backlog is small. It is conjectured that suchideal system behavior can be approached using a family of relatively simple schedulingpolicies related to the cµ rule.Keywords: heavy traffic, parallel-server systems, Brownian control problem, resource pool-ing1. IntroductionThis paper is concerned with dynamic scheduling of stochastic processing systemsthat have the following general structure (see figure 1). There are job classes indexedby i = 1, ..., m and servers indexed by k = 1, ..., r. Jobs of each class arrivefrom outside the system and require a single service before they depart. Severaldifferent servers may be capable of processing any given job class, and the service J.C. Baltzer AG, Science Publishers340 J.M. Harrison, M.J. L´opez / Heavy traffic resource poolingFigure 1. Example of a parallel-server system.time distribution depends on both the class being processed and the server selected.(Here and later, we speak in terms of processing jobs rather than serving customers,but the terms “server” and “service time” are used in preference to “processor” and“processing time”.) Thus there are n 6 mr processing activities available to thesystem manager, each of which consists of a particular server processing a particularjob class. For each activity j = 1,..., n we denote by i(j) the job class processedin that activity, and by k(j) the server that does the processing. Also, let j(i, k)bethe activity in which server k processes class i (if there is one). Models having thestructure described in this paragraph will be referred to hereafter as parallel-serversystems.For concreteness, we assume that the system is initially empty, and that servicesmust be completed without interruption once they have been started, but neither of thoseassumptions is really important for the results ultimately obtained. It is convenient toimagine that jobs reside in buffers dedicated to their respective classes until they areready to be processed (buffers are represented by open-ended rectangles in figure 1).The system manager need not specify which server will process a given job until theprocessing is to begin. Finally, holding costs are continuously incurred at a rate ofcidollars per time unit for each class i job in the system, either waiting or beingserved. For future purposes, let us denote by λithe average arrival rate for class ijobs (i = 1, ..., m) and by µjthe reciprocal of the mean service time for activity j(j = 1, ..., n). In the usual way, µjwill often be referred to as the “mean servicerate” for activity j.Roughly speaking, the scheduling problem confronted by the system manager isone of dynamically allocating jobs to servers so that holding costs are minimized. Inthe interest of concreteness, readers may think in terms of minimizing long-run averagecost per time unit, or of minimizing expected cost incurred up to a finite but distant timehorizon, but for reasons explained below, our analysis is actually applicable under anyoptimality criterion that involves costs accumulated over relatively long time spans. AtJ.M. Harrison, M.J. L´opez / Heavy traffic resource pooling 341the mechanical level, a scheduling policy must specify, each time a server completesthe processing of a job, which class that server will work on next. Also, each timea job arrives and finds one or more of its servers idle, the scheduling policy mustspecify which server will process that job. Of course, the scheduling policy must benon-anticipating in the sense that each decision is based solely on information availableat the decision point. In the language of queueing network theory [5,12], the systemmanager’s problem involves both routing decisions and sequencing decisions. That is,decisions must be made as to which job classes will be directed to which servers, andas to the order in which servers will process jobs from the various buffers. It is theopportunity for dynamic alternate routing that gives the problem its distinctive flavor.Even in the simplest case with independent Poisson arrival processes, exponen-tially distributed service times for all activities, and a long-run average cost criterion,the dynamic scheduling problem described above defies exact solution. This is a typi-cal difficulty in the study of stochastic processing networks, and for that reason, authorsoften resort to asymptotic