关于轮询系统的竞争分析（CS PF）
- 2020 年 1 月 14 日
- 笔记
轮询系统已被广泛研究，但这些研究大多集中在轮询系统更新过程的到达和服务时间的随机变量。在实际应用程序的驱动下，需要研究具有任意到达(不限于时变或成批)的轮询系统，并在作业到达时显示服务时间。为了满足这一需求，我们的工作考虑了一个具有通用设置的轮询系统，并首次为该系统中的在线调度策略提供了最坏的情况分析。给出了该系统存在常竞争比的条件，并给出了循环穷举策略、门控策略和有限策略、随机最大队列策略、单机策略和轮询系统的Gittins指数策略等几个研究比较深入的策略的竞争比。我们证明(1)纯静态、(2)基于队列长度或(3)基于作业处理时间的路由规则的任何策略的竞争比都不小于[数学处理错误]，其中[数学处理错误]是队列的数量。最后，针对实际情况提出了一种混合策略。
原文题目：On Competitive Analysis for Polling Systems
原文：Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratio for this system, and also the competitive ratios for several well-studied policies such as cyclic exhaustive, gated and emph{l}-limited policies, Stochastic Largest Queue policy, One Machine policy and Gittins Index policy for polling systems. We show that any policy with (1) purely static, (2) queue-length based or (3) job-processing-time based routing discipline does not have a competitive ratio smaller than [Math Processing Error], where [Math Processing Error] is the number of queues. Finally, a mixed strategy is provided for a practical scenario where setup time is large but bounded.
原文作者：Jin Xu, Natarajan Gautam
原文地址：https://arxiv.org/abs/2001.02530
