On competitive analysis for polling systems
From MaRDI portal
Publication:6072151
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.
Recommendations
Cites work
- A class of on-line scheduling algorithms to minimize total completion time
- A new approach to online scheduling: approximating the optimal competitive ratio
- A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness
- A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times
- A survey of scheduling problems with setup times or costs
- Achievable performance of blind policies in heavy traffic
- An online algorithm for a problem in scheduling with set-ups and release times
- An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
- Analysis of queues. Methods and applications
- Approximation algorithms for scheduling unrelated parallel machines
- Approximation techniques for average completion time scheduling
- Competitive analysis of preemptive single-machine scheduling
- Delays at signalized intersections with exhaustive traffic control
- Efficient visit orders for polling systems
- Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems—Exact Results and Applications
- Is tail-optimal scheduling possible?
- Iterative approximation of \(k\)-limited polling systems
- Lower bounds for on-line single-machine scheduling.
- Mathematical methods to study the polling systems
- Mean value analysis for polling systems
- Minimizing average completion time in the presence of release dates
- Minimizing flow-time on a single machine with integer batch sizes
- Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
- On Elevator polling with globally gated regime
- On optimal polling policies
- On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times.
- On two-queue Markovian polling systems with exhaustive service
- Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
- Online machine scheduling with family setups
- Optimal on-line algorithms for single-machine scheduling
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Performance analysis of Markovian polling systems with single buffers
- Polling models with multi-phase gated service
- Polling-Systems-Based Autonomous Vehicle Coordination in Traffic Intersections With No Traffic Signals
- Queuing analysis of polling models
- Randomized algorithms for on-line scheduling problems: How low can't you go?
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Single machine scheduling with release dates
- Solving the flexible job shop scheduling problem with sequence-dependent setup times
- Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline
- The hybrid flow shop scheduling problem
- The power of \(\alpha\)-points in preemptive single machine scheduling.
- The significance of reducing setup times/setup costs
- The third comprehensive survey on scheduling problems with setup times/costs
Cited in
(5)- Dominance relations in polling systems
- Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions
- scientific article; zbMATH DE number 4147805 (Why is no real title available?)
- scientific article; zbMATH DE number 19790 (Why is no real title available?)
- Belated analyses of three credit-based adaptive polling algorithms
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)
