The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions
The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions
复制标题
在极其一般的条件下，Gittins 策略在 M/G/k 中几乎是最优的
DOI：
10.1145/3428328
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Harchol-Balter, Mor
中科院分区：
文献类型：
--
作者：
Scully, Ziv;Grosof, Isaac;Harchol-Balter, Mor
在各种设置下，Gittins调度策略将单服务器M/G/1队列中的平均响应最小化。最著名的是，当允许抢占并且服务需求未知但来自已知发行版时，Gittins是最佳的。一般而言，Gittins也是最优的，可以适应任何数量的可用信息和任何抢占限制。然而，在多服务器环境中，特别是在中央队列M/G/k中，最小化平均响应时间的调度是一个困难得多的问题。在这项工作中，我们首先给出了Gittins在M/G/k中的一般分析.具体地说，我们证明了在极其一般的条件下，Gittins在M/G/k中的平均响应时间至多是它在M/G/1加上一个加性项的平均响应时间，其中ρ是系统负载.这一结果的结果是，如果服务需求分布S满足$\mathbfE[S^2(łog S)^+]<；\inty$，则Gittins在M/G/k中是大流量最优的。这是迄今为止关于最小化M/G/k中的平均响应时间的最一般结果。为了证明我们的结果，我们以一种新颖的方式结合了Gittins策略和Palm演算的性质。值得注意的是，我们的技术克服了先前调度分析中使用的标记作业方法的局限性。
The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M/G/k, is a much more difficult problem. In this work we give the first general analysis of Gittins in the M/G/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M/G/k is at most its mean response time in the M/G/1 plus anadditive term, where ρ is the system load. A consequence of this result is that Gittins is heavy-traffic optimal in the M/G/k if the service requirement distribution S satisfies $\mathbfE [S^2(łog S)^+] < \infty$. This is the most general result on minimizing mean response time in the M/G/k to date. To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses.
登录
查看更多内容
GITTINS 指数的特性及其在优化调度中的应用
DOI：
10.1017/s0269964811000015
发表时间：
2011
影响因子：
1.1
作者：
S. Aalto;U. Ayesta;Rhonda Righter
通讯作者：
Rhonda Righter
多臂老虎机、Gittins 指数及其计算
DOI：
10.1002/9781118596333.ch24
发表时间：
2014
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Jhelum Chakravorty;Aditya Mahajan
通讯作者：
Aditya Mahajan
临床试验中统计学的方法和应用：计划、分析和推理方法
DOI：
10.1002/9781118596333
发表时间：
2014
期刊：
Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications
影响因子：
--
作者：
N. Balakrishnan
通讯作者：
N. Balakrishnan
速率守恒定律：一项调查
影响因子：
1.2
作者：
M. Miyazawa
通讯作者：
M. Miyazawa
多服务器系统的 SRPT
DOI：
10.1016/j.peva.2018.10.001
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
Isaac Grosof;Ziv Scully;Mor Harchol
通讯作者：
Mor Harchol