Dynamic Scheduling of a System with Two Parallel Servers in Heavy
Traffic with Complete Resource Pooling:
Asymptotic Optimality of a Continuous Review
Threshold Policy
S. L. Bell and R. J. Williams
Abstract
This paper concerns a dynamic scheduling problem for a queueing
system that has
two streams of
arrivals to infinite capacity
buffers and
two (non-identical) servers working
in parallel.
One server can only process jobs from one buffer, whereas
the other server can process jobs from either buffer.
The service time distribution may depend on the buffer
being served and the server providing the service.
The system manager dynamically schedules
waiting jobs onto available servers.
We consider a parameter regime
in which the system satisfies
both a heavy traffic condition and a
resource pooling condition. Our cost function
is a mean cumulative discounted cost of holding
jobs in the system, where the (undiscounted) cost per unit
time is a linear function of normalized (with heavy traffic scaling)
queue length.
We first review the
analytic solution of the
Brownian control problem (formal
heavy traffic approximation) for this system.
We ``interpret" this solution by
proposing
a ``continuous review" threshold control policy
for use in the original parallel server
system. We show that this policy is asymptotically optimal in the
heavy traffic limit and the limiting cost is the same as the optimal
cost in the Brownian control problem.
The techniques developed here are
expected to be useful for analyzing
the performance of threshold-type policies in
more complex multiserver
systems.
This paper appears in the Annals of Applied Probability, 11 (2001), 608-649. The final printed version of the article is freely available through open access on
Project Euclid by clicking here.