Optimal routing in output-queued flexible server systems

We consider a queueing system with multi-type customers and non-homogeneous exible servers, in the heavy traÆc asymptotic regime and under a complete resource pooling (CRP) condition. For the input-queued (IQ) version of such a system (with cus-tomers being queued at the system \entrance, " one queue per each type), it was shown in [12] that a simple parsimonious Gc scheduling rule is optimal in that it asymp-totically minimizes the system customer workload and some strictly convex queueing costs. In this paper we consider a dierent- output-queued (OQ)- version of the model, where each arriving customer must be assigned to one of the servers immediately upon arrival. (This constraint can be interpreted as immediate routing of each customer to one of the \output queues, " one queue per each server.) Consequently, the space of controls allowed for an OQ-system is a subset of that for the corresponding IQ-system. We introduce the MinDrift routing rule for OQ-systems (which is as simple and parsimonious as Gc), and show that this rule, in conjunction with arbitrary work-conserving disciplines at the servers, has asymptotic optimality properties analogous to those Gc-rule has for IQ-systems. A key element of the analysis is the notion of system server workload, which, in particular, majorizes customer workload. We show that (i) MinDrift-rule asymptotically minimizes server workload process among all OQ-system disciplines and (ii) this minimal process matches the minimal possible customer workload process in the corresponding IQ-system. As a corollary, MinDrift asymptotically minimizes customer workload among all disciplines in either the OQ-or IQ-system