Primal-dual analysis for online interval scheduling problems

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)575-602
Number of pages28
JournalJournal of Global Optimization
Volume77
Issue number3
DOIs
StateAccepted/In press - Jan 1 2020

    Fingerprint

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

Cite this