论文标题
针对轮换系统的二项式避免政策的渐近最佳性，切换时间较大
Asymptotic Optimality of the Binomial-Exhaustive Policy for Polling Systems with Large Switchover Times
论文作者
论文摘要
我们研究了在队列上产生持有成本时，转换时间较大的投票系统的最佳控制问题。特别是，我们考虑一个随机网络，该网络具有单个服务器，该网络根据预先指定的顺序在几个缓冲区（队列）之间切换，假设队列之间的切换时间相对于单个作业的处理时间很大。由于其复杂性，计算该系统的最佳控制是非常令人难以置信的，因此我们改为搜索渐近的最佳控制。为此，我们首先解决了确定性放松的最佳控制问题（即流体模型），该问题被表示为混合动力学系统。然后，我们将解决方案转化为基础随机系统的二项式避免策略，并证明该策略在大型转换时间缩放率方面均无最佳，提供了一定的统一的可集成性（UI）条件。最后，我们证明了上述UI条件在以下情况下存在：（i）持有成本（最多）线性增长，所有服务时间都有有限的第二瞬间； （ii）保持成本最多以多项式速率（任何程度）增长，并且服务时间分布具有有限的力矩生成功能。
We study an optimal-control problem of polling systems with large switchover times, when a holding cost is incurred on the queues. In particular, we consider a stochastic network with a single server that switches between several buffers (queues) according to a pre-specified order, assuming that the switchover times between the queues are large relative to the processing times of individual jobs. Due to its complexity, computing an optimal control for such a system is prohibitive, and so we instead search for an asymptotically optimal control. To this end, we first solve an optimal control problem for a deterministic relaxation (namely, for a fluid model), that is represented as a hybrid dynamical system. We then "translate" the solution to that fluid problem to a binomial-exhaustive policy for the underlying stochastic system, and prove that this policy is asymptotically optimal in a large-switchover-time scaling regime, provided a certain uniform integrability (UI) condition holds. Finally, we demonstrate that the aforementioned UI condition holds in the following cases: (i) the holding cost has (at most) linear growth, and all service times have finite second moments; (ii) the holding cost grows at most at a polynomial rate (of any degree), and the service-time distributions possess finite moment generating functions.
