OPTIMAL-CONTROL OF MULTICLASS PARALLEL SERVICE SYSTEMS

We consider routing and scheduling systems consisting of a number of p arallel homogeneous servers with finite capacities. Assuming that jobs belong to multiple classes, we represent the interconnection of arriv al streams (servers) to stations by a bipartite graph, called the rout ing (reap. scheduling) digraph. By developing an algebraic structure o n the interconnection pattern embedded in the digraph, we identify cer tain classes of symmetric routing and scheduling systems for which a s imple control policy such as the Shortest Queue policy can be shown to be optimal in the sense of optimizing the departure and loss counting processes. A counterexample is shown for systems described by digraph s with a cyclic structure.