Optimal multiserver scheduling with unknown job sizes in heavy traffic
Optimal multiserver scheduling with unknown job sizes in heavy traffic
复制标题
高流量下未知作业大小的最佳多服务器调度
DOI：
10.1016/j.peva.2020.102150
复制
发表时间：
2021
影响因子：
2.2
通讯作者：
Harchol-Balter, Mor
中科院分区：
文献类型：
--
作者：
Scully, Ziv;Grosof, Isaac;Harchol-Balter, Mor
我们考虑调度以最小化作业规模未知的M/G/k队列的平均响应时间。在单服务器k = 1的情况下，最优策略是Gittins策略，但不知道Gittins或任何其他策略在多服务器情况下是最优的。准确地分析任何调度策略下的M/G/k都是棘手的，Gittins是一个特别复杂的策略，即使在单服务器的情况下也很难分析。在这项工作中，我们引入单调Gittins (M-Gittins)，这是Gittins策略的一种新变体，并表明它在大流量M/G/k中最小化了一类有限方差作业大小分布的平均响应时间。我们还表明，单调最短预期剩余处理时间（M- serpt）策略比M- gittins策略更简单，在类似条件下，它是高流量M/G/k下平均响应时间的2近似。这些结果构成了迄今为止具有未知作业规模的M/G/k的最一般最优性结果。我们的技术建立在Grosof等人的工作基础上，他们研究了M/G/k中的简单策略，如SRPT；Bansal et al. [2], Kamphorst and Zwart [7], Lin et al.[9]，他们分析了大流量M/G/1中简单策略的平均响应时间尺度；以及Aalto et al.[1]和Scully et al.[11,13]，他们对M/G/1中的gittin策略进行了表征和分析。
We consider scheduling to minimize mean response time of the M/G/k queue with unknown job sizes. In the singleserver k = 1 case, the optimal policy is the Gittins policy, but it is not known whether Gittins or any other policy is optimal in the multiserver case. Exactly analyzing the M/G/k under any scheduling policy is intractable, and Gittins is a particularly complicated policy that is hard to analyze even in the single-server case.In this work we introduce monotonic Gittins (M-Gittins), a new variation of the Gittins policy, and show that it minimizes mean response time in the heavy-traffic M/G/k for a wide class of finite-variance job size distributions. We also show that the monotonic shortest expected remaining processing time (M-SERPT) policy, which is simpler than M-Gittins, is a 2-approximation for mean response time in the heavy traffic M/G/k under similar conditions. These results constitute the most general optimality results to date for the M/G/k with unknown job sizes. Our techniques build upon work by Grosof et al. [6], who study simple policies, such as SRPT, in the M/G/k; Bansal et al. [2], Kamphorst and Zwart [7], and Lin et al. [9], who analyze mean response time scaling of simple policies in the heavy-traffic M/G/1; and Aalto et al. [1] and Scully et al. [11, 13], who characterize and analyze the Gittins policy in the M/G/1.