Abstract
Online interval scheduling problems consider scheduling a sequence of jobs on machines to maximize the total reward. Various approaches and algorithms have been proposed for different problem formulations. This paper provides a primal-dual approach to analyze algorithms for online interval scheduling problems. This primal-dual technique can be used for both stochastic and adversarial job sequences, and hence, is universally and generally applicable. We use strong duality and complementary slackness conditions to derive exact algorithms for scheduling stochastic equal-length job sequences on a single machine. We use weak duality to obtain upper bounds for the optimal reward for scheduling stochastic equal-length job sequences on multiple machines and C-benevolent job sequences on a single machine.
Original language | English (US) |
---|---|
Pages (from-to) | 575-602 |
Number of pages | 28 |
Journal | Journal of Global Optimization |
Volume | 77 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1 2020 |
Keywords
- Online algorithms
- Online interval scheduling
- Primal-dual analysis
ASJC Scopus subject areas
- Computer Science Applications
- Management Science and Operations Research
- Control and Optimization
- Applied Mathematics