On competitive analysis for polling systems
From MaRDI portal
Publication:6072151
DOI10.1002/NAV.21926zbMATH Open1523.90093arXiv2001.02530OpenAlexW3106126173MaRDI QIDQ6072151FDOQ6072151
Authors: Jin Xu, Natarajan Gautam 
Publication date: 12 October 2023
Published in: Naval Research Logistics (Search for Journal in Brave)
Abstract: 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 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.
Full work available at URL: https://arxiv.org/abs/2001.02530
Recommendations
Queues and service in operations research (90B22) Deterministic scheduling theory in operations research (90B35)
Cites Work
- The hybrid flow shop scheduling problem
- Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times.
- A survey of scheduling problems with setup times or costs
- Approximation algorithms for scheduling unrelated parallel machines
- A class of on-line scheduling algorithms to minimize total completion time
- Lower bounds for on-line single-machine scheduling.
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Optimal on-line algorithms for single-machine scheduling
- Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
- The significance of reducing setup times/setup costs
- Minimizing flow-time on a single machine with integer batch sizes
- The third comprehensive survey on scheduling problems with setup times/costs
- Analysis of queues. Methods and applications
- Efficient visit orders for polling systems
- Delays at signalized intersections with exhaustive traffic control
- Mathematical methods to study the polling systems
- Single machine scheduling with release dates
- A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times
- An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
- On optimal polling policies
- Queuing analysis of polling models
- Minimizing average completion time in the presence of release dates
- Approximation techniques for average completion time scheduling
- Polling models with multi-phase gated service
- On two-queue Markovian polling systems with exhaustive service
- An online algorithm for a problem in scheduling with set-ups and release times
- Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline
- Mean value analysis for polling systems
- The power of \(\alpha\)-points in preemptive single machine scheduling.
- Competitive analysis of preemptive single-machine scheduling
- Iterative approximation of \(k\)-limited polling systems
- A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness
- Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems—Exact Results and Applications
- Is tail-optimal scheduling possible?
- Solving the flexible job shop scheduling problem with sequence-dependent setup times
- Randomized algorithms for on-line scheduling problems: How low can't you go?
- Performance analysis of Markovian polling systems with single buffers
- On Elevator polling with globally gated regime
- A new approach to online scheduling: approximating the optimal competitive ratio
- Online machine scheduling with family setups
- Polling-Systems-Based Autonomous Vehicle Coordination in Traffic Intersections With No Traffic Signals
- Achievable performance of blind policies in heavy traffic
Cited In (5)
This page was built for publication: On competitive analysis for polling systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072151)
