On Dynamic Scheduling of a Parallel Server System with Certain Graph Structure

We consider a problem of dynamic scheduling for a parallel server system. This system consists of finitely many infinite capacity buffers (classes) for holding incoming jobs awaiting service and finitely many non-identical servers working in parallel. Jobs within each buffer are served on a first-in-first-out basis. Each job requires a single service before it leaves the system. Each server can work on at most one job at a time, but it may be capable of processing several different classes of jobs over time, and it may suspend service of a job to work on a job of another class. Jobs of a given class incur holding costs at a rate proportional to the number of jobs in the class at each instant of time. The system manager seeks to minimize a cumulative discounted holding cost by dynamically scheduling waiting jobs to available servers. Following a method introduced by Harrison, for this parallel server system in heavy traffic we approximate the scheduling control problem by a Brownian control problem (BCP), which can be reduced to an Equivalent Workload Formulation (EWF). We first prove that the server-buffer graph, consisting of servers and buffers linked by basic activities, is a forest of trees. Then we give sufficient conditions for a least control process to be the optimal solution of the EWF. Under these conditions, we propose a continuous review threshold-type control policy that exploits partial pooling of servers. We conjecture that this policy is asymptotically optimal for the original parallel server system in the heavy traffic limit. To illustrate the solution of the EWF, and our proposed control policy for the original network we give a three buffer, three server example. We prove that this control policy is asymptotically optimal for this example in the heavy traffic limit. This is the first instance of a proof of asymptotic optimality for a parallel server system with partial pooling is the usual heavy traffic regime.