论文标题
在流量繁忙的情况下，最佳的多力量计划的工作规模未知
Optimal Multiserver Scheduling with Unknown Job Sizes in Heavy Traffic
论文作者
论文摘要
我们考虑安排以未知的工作规模最小化M/g/k队列的平均响应时间。在单人行为的情况下，最佳策略是Gittins策略，但尚不清楚Gittins或任何其他策略在多层案例中是否最佳。准确地分析任何调度策略下的M/G/K是棘手的，而Gittins是一项特别复杂的政策，即使在单服务器案例中也很难分析。 在这项工作中，我们介绍了Gittins政策的新变体单调GITTINS（M-GITTINS），并表明它可以最大程度地减少繁重的M/G/K中的平均响应时间，用于广泛的有限变化的工作规模分布。我们还表明，单调最短的剩余处理时间（M-SERPT）策略（比M-Gittins更简单）是在类似条件下繁重的流量M/G/K中平均响应时间的2个附属物。这些结果构成了迄今为止的最佳最佳结果，对于未知的工作规模的M/G/K。我们的技术建立在Grosof等人的工作基础上，Grosof等人在M/g/k中研究了简单的政策，例如SRPT； Bansal等人，Kamphorst和Zwart和Lin等人，他们分析了重型M/G/1中简单策略的平均响应时间缩放；和Aalto等。和Scully等人，他在M/G/1中表征和分析Gittins政策。
We consider scheduling to minimize mean response time of the M/G/k queue with unknown job sizes. In the single-server 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., who study simple policies, such as SRPT, in the M/G/k; Bansal et al., Kamphorst and Zwart, and Lin et al., who analyze mean response time scaling of simple policies in the heavy-traffic M/G/1; and Aalto et al. and Scully et al., who characterize and analyze the Gittins policy in the M/G/1.
