OPTIMAL-CONTROL OF A MULTICLASS, FLEXIBLE QUEUING SYSTEM

We consider a general class of queueing systems with multiple job type s and a flexible service facility. The arrival limes and sizes of inco ming jobs are random, and correlations among the sizes of arriving job types are allowed. By choosing among a finite set of configurations, the facility can dynamically control the rates at which it serves the various job types. We define system work at any given time as the mini mum time required to process all jobs currently in the backlog. This q uantity is determined by solving a linear program defined by the set o f processing configurations. The problem we study is how to dynamicall y choose configurations to minimize the time average system work. Usin g bounds and heuristics, we analyze a class of service policies that i s provably asymptotically optimal as system utilization approaches one , as well as a policy that in numerical studies performs near-optimall y in moderate traffic. Our analysis also yields a closed-form expressi on for the optimal, average work in heavy traffic. This general proble m has a number of applications in job shop and flexible manufacturing, in service organizations, and in the management of parallel processin g and distributed database systems.