PROPERTIES OF THE GITTINS INDEX WITH APPLICATION TO OPTIMAL SCHEDULING
PROPERTIES OF THE GITTINS INDEX WITH APPLICATION TO OPTIMAL SCHEDULING
复制标题
GITTINS 指数的特性及其在优化调度中的应用
DOI：
10.1017/s0269964811000015
复制
发表时间：
2011
影响因子：
1.1
通讯作者：
Rhonda Righter
中科院分区：
文献类型：
--
作者：
S. Aalto;U. Ayesta;Rhonda Righter
我们考虑了没有到达的单人队列的最佳调度问题。我们允许先发制人，我们的目的是最大程度地减少预期流动时间。已知最佳的非预期学科是Gittins指数策略，但是，该策略是以隐式方式定义的。到目前为止，仅在少数特殊情况下，其在此特定问题中的一般行为才得到表征。在本文中，我们给出了尽可能完整的表征。事实证明，最佳政策始终属于多级处理器共享学科的家族。
We consider the optimal scheduling problem for a single-server queue without arrivals. We allow preemptions, and our purpose is to minimize the expected flow time. The optimal nonanticipating discipline is known to be the Gittins index policy, which, however, is defined in an implicit way. Until now, its general behavior in this specific problem has been characterized only in a few special cases. In this article, we give as complete a characterization as possible. It turns out that the optimal policy always belongs to the family of multilevel processor sharing disciplines.