Dynamic scheduling of a parallel server system in heavy traffic with complete resource pooling: Asymptotic optimality of a threshold policy

We consider a queueing system with a bank of non-identical servers working in parallel, exogenous arrivals classified into one of several infinite capacity buffers, and linear holding costs for each buffer. Jobs within a buffer are ordered on a first-in-first-out basis. Each incoming job requires a single service which may be provided by any of several different servers; the service time of a job may depend on both its buffer and the server providing the service. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs to available servers. In a recent work, under a complete resource pooling condition, Williams [39] proposed a continuous review threshold control policy for such a parallel server system by “interpreting” the analytic solution to the associated Brownian control problem (formal heavy traffic approximation). We show that this policy is asymptotically optimal in the heavy traffic limit and that the limiting cost is the same as the optimal cost in the Brownian control problem.