A service system with multiple types of arriving customers is considered.There is an infinite number of homogeneous servers. Multiple customers can beplaced for simultaneous service into one server, subject to general packingconstraints. Each new arriving customer is placed for service immediately,either into an occupied server, as long as packing constraints are notviolated, or into an empty server. After service completion, each customerleaves its server and the system. The basic objective is to minimize the numberof occupied servers in steady state. We study a Greedy-Random (GRAND) placement(packing) algorithm, introduced in [23]. This is a simple online algorithm,which places each arriving customer uniformly at random into either one of thealready occupied servers that can still fit the customer, or one of theso-called zero-servers, which are empty servers designated to be available tonew arrivals. In [23], a version of the algorithm, labeled GRAND($aZ$), wasconsidered, where the number of zero servers is $aZ$, with $Z$ being thecurrent total number of customers in the system, and $a>0$ being an algorithmparameter. GRAND($aZ$) was shown in [23] to be asymptotically optimal in thefollowing sense: (a) the steady-state optimality gap grows linearly in thesystem scale $r$ (the mean total number of customers in service), i.e. as $c(a)r$ for some $c(a)> 0$; and (b) $c(a) o 0$ as $ao 0$. In this paper, weconsider the GRAND($Z^p$) algorithm, in which the number of zero-servers is$Z^p$, where $p in (1-1/(8kappa),1)$ is an algorithm parameter, and$(kappa-1)$ is the maximum possible number of customers that a server can fit.We prove the asymptotic optimality of GRAND($Z^p$) in the sense that thesteady-state optimality gap is $o(r)$, sublinear in the system scale. This is astronger form of asymptotic optimality than that of GRAND($aZ$).
展开▼
机译：考虑使用多种到达客户的服务系统。有一个无限数量的同类服务器。多个客户可以脱落，以便同时服务进入一台服务器，受通用PackingConstraints。每个新的到达客户都将立即放置到占用服务器中，只要包装约束都不润滑，或者在空服务器中。完成后完成后，每个客户服务器和系统。基本目标是最大限度地减少稳定状态的占用服务器的数量。我们研究了一种贪婪的随机（Grand）放置（包装）算法，在[23]中介绍。这是一个简单的在线算法，每个客户都以随机的方式统一地放入一个仍然适合客户的Thealready占用服务器之一，或者称为归零服务器之一，它是指定为可用的Tonew到达的空服务器。在[23]中，算法的版本，标记为Grand（$ Az $），归功于零级服务器的数量为$ az $，$ z $在系统中为您的客户总数和$ a> 0 $是算法参数。在[23]中展示了大（$ AZ $）在关注的情况下渐近最佳：（a）稳态最优差距在和服务中线性地增长，即服务的平均总数），即$ C（a）r $的$ c（a）> 0 $; （b）$ c（a）至0 $ a $ 0 $。在本文中，WeConsider The Grand（$ Z ^ P $）算法，其中零架的数量是$ z ^ p $，其中$ p in（1-1 /（8 kappa），1）$是一个算法参数，$（ kappa-1）$是服务器可以融合的最大可能数量的客户。我们在博物常态最优差距的意义上证明了宏观（$ z ^ p $）的渐近最优性在系统规模中是$ o（r）$，sublinear。这是渐近最优性的星星形式，而不是盛大（$ az $）。
展开▼
