Interval scheduling : a survey

A.W.J. Kolen, J.K. Lenstra, C.H. Papadimitriou, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

138 Citations (Scopus)

Abstract

In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given maximal machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution.
Original languageEnglish
Pages (from-to)530-543
JournalNaval Research Logistics
Volume54
Issue number5
DOIs
Publication statusPublished - 2007

Fingerprint

Dive into the research topics of 'Interval scheduling : a survey'. Together they form a unique fingerprint.

Cite this