An Infinite Server System with General Packing Constraints
成果类型：
Article
署名作者：
Stolyar, Alexander L.
署名单位：
AT&T; Alcatel-Lucent
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2013.1184
发表日期：
2013
页码：
1200-1217
关键词：
摘要：
We consider a service system model primarily motivated by the problem of efficient assignment of virtual machines to physical host machines in a network cloud, so that the number of occupied hosts is minimized. There are multiple input flows of different type customers, with a customer mean service time depending on its type. There is an infinite number of servers. A server-packing configuration is the vector k = {k(i)}, where k(i) is the number of type i customers the server contains. Packing constraints must be observed; namely, there is a fixed finite set of configurations k that are allowed. Service times of different customers are independent; after a service completion, each customer leaves its server and the system. Each new arriving customer is placed for service immediately; it can be placed into a server already serving other customers (as long as packing constraints are not violated), or into an idle server. We consider a simple parsimonious real-time algorithm, called Greedy, that attempts to minimize the increment of the objective function Sigma(k)Sigma(l+d)(k), alpha > 0, caused by each new assignment; here X-k is the number of servers in configuration k. (When a is small, Sigma X-k(k)l+alpha approximates the total number Sigma X-k(k) of occupied servers.) Our main results show that certain versions of the Greedy algorithm are asymptotically optimal, in the sense of minimizing Sigma X-k(k)l+alpha in stationary regime as the input flow rates grow to infinity. We also show that in the special case when the set of allowed configurations is determined by vector-packing.constraints, the Greedy algorithm can work with aggregate configurations as opposed to exact configurations k, thus reducing computational complexity while preserving the asymptotic optimality.
来源URL：