關於輪詢系統的競爭分析（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
