
arXiv: 2001.02530
AbstractPolling 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 ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well‐studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l‐limited service disciplines for polling systems.
FOS: Computer and information sciences, Computer Science - Performance, Discrete Mathematics (cs.DM), Deterministic scheduling theory in operations research, worst-case analysis, competitive ratio, parallel queues with setup times, Performance (cs.PF), online algorithm, Optimization and Control (math.OC), FOS: Mathematics, scheduling, Queues and service in operations research, Mathematics - Optimization and Control, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Computer Science - Performance, Discrete Mathematics (cs.DM), Deterministic scheduling theory in operations research, worst-case analysis, competitive ratio, parallel queues with setup times, Performance (cs.PF), online algorithm, Optimization and Control (math.OC), FOS: Mathematics, scheduling, Queues and service in operations research, Mathematics - Optimization and Control, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
