Interval scheduling: A survey |
| |
Authors: | Antoon WJ Kolen Jan Karel Lenstra Christos H Papadimitriou Frits CR Spieksma |
| |
Institution: | 1. Department of Quantitative Economics, Maastricht University, NL‐6200 MD Maastricht, The Netherlands;2. Antoon Kolen sadly passed away on October 3, 2004. His coauthors dedicate their contribution to this paper to his memory.;3. Center for Mathematics and Computer Science, NL‐1090 GB Amsterdam, The Netherlands;4. Computer Science Division, University of California, Berkeley, California 94720;5. Department of Operations Research and Business Statistics, Katholieke Universiteit Leuven, Naamsestraat 69, B‐3000, Leuven, BelgiumDepartment of Operations Research and Business Statistics, Katholieke Universiteit Leuven, Naamsestraat 69, B‐3000, Leuven, Belgium |
| |
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. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007 |
| |
Keywords: | analysis of algorithms computational complexity: exact algorithms production/scheduling sequencing deterministic: interval scheduling |
|
|