OPTIMAL ROUTING IN OUTPUT-QUEUED FLEXIBLE SERVER SYSTEMS
OPTIMAL ROUTING IN OUTPUT-QUEUED FLEXIBLE SERVER SYSTEMS
复制标题
输出排队灵活服务器系统中的最优路由
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Stolyar
中科院分区：
文献类型：
--
作者：
A. Stolyar
研究了一类具有多类型顾客和非齐次柔性服务台的排队系统，在大流量渐近区域和完全资源池条件下。对于这种系统的输入排队（IQ）版本（客户在系统的“入口”排队，每种类型一个队列），Mandelbaum和Stolyar的工作表明，一个简单的简约Gcμ调度规则是最优的，因为它渐近最小化系统客户的工作量和一些严格凸排队成本。在这篇文章中，我们考虑一个不同的输出排队（OQ）模型版本，其中每个到达的客户必须在到达时立即分配到其中一个服务器。(This约束可以被解释为每个客户直接路由到“输出队列”之一，每个服务器一个队列。因此，OQ系统允许的控制空间是相应IQ系统的子集。我们介绍了MinDrift路由规则的OQ系统（这是简单和吝啬的Gcμ），并表明，这一规则，结合任意的工作保存在服务器上的纪律，具有渐近最优性类似于那些Gcμ规则的IQ系统。分析的一个关键要素是系统服务器工作负载的概念，特别是优化客户工作负载。我们表明，（1）MinDrift规则渐近最小化服务器的工作负载过程中的所有OQ系统的纪律和（2）这个最小的过程相匹配的最小可能的客户工作负载过程中相应的IQ系统。作为推论，MinDrift在OQ或IQ系统中的所有学科中渐进地最小化客户工作负载。
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 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 (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.