Optimal Routing in Output-Queued Flexible Server Systems

We consider a queueing system with multi-type customers and non-homogeneous 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 [12] that a simple parsimonious 'Gc-mu' scheduling rule is optimal in that it asymptotically minimizes the system 'customer workload' and some strictly convex queueing costs. In this paper 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 Gc-mu), and show that this rule, in conjunction with arbitrary work-conserving disciplines at the servers, has asymptotic optimality properties analogous to those Gc-mu-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.