Optimal routing in output-queued flexible server systems

We consider a queuing system with multitype customers and nonhomogeneous flexible servers, in the heavy traffic asymptotic regime and under a complete resource pooling (CRP) condition. For the input-queued (IQ) version of such a system (with customers being queued at the system "entrance," one queue per each type), it was shown in the work of Mandelbaum and Stolyar that a simple parsimonious Gcμ scheduling rule is optimal in that it asymptotically minimizes the system customer workload and some strictly convex queuing costs. In this article, we consider a different - 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 Gen) and show that this rule, in conjunction with arbitrary work-conserving disciplines at the servers, has asymptotic optimality properties analogous to those Gcyj 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 (1) the MinDrift rule asymptotically minimizes server workload process among all OQ-system disciplines and (2) 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.