Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 220

The DOI matches its Crossref record.

Interval scheduling: A survey

Open access
Kolen, Antoon W.J., Lenstra, Jan Karel, Papadimitriou, Christos H., Spieksma, Frits C.R.·2007·Naval Research Logistics (NRL)
DOI 10.1002/nav.20231
Open this paper in CoChat — free account

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

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1002/nav.20231

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 70

  1. Ahuja R. K., 1993, Network flows
  2. 10.1016/0377-2217(84)90095-X · doi:10.1016/0377-2217(84)90095-x
  3. 10.1016/0166-218X(87)90037-0 · DOI
  4. 10.1145/502102.502107 · doi:10.1145/502102.502107
  5. 10.1137/S0097539797321237 · doi:10.1137/s0097539797321237
  6. 10.1137/S0097539799354138 · DOI
  7. 10.1016/S0305-0548(98)00019-7 · doi:10.1016/s0305-0548(98)00019-7
  8. 10.1023/A:1009822211065 · doi:10.1023/a:1009822211065
  9. 10.1007/3-540-45061-0_59 · doi:10.1007/3-540-45061-0_59
  10. 10.1016/0012-365X(92)90646-W · doi:10.1016/0012-365x(92)90646-w
  11. Borodin A., 1988, On‐Line computation and competitive analysis
  12. K. I.Bouzina On interval scheduling problems: A contribution Ph.D. Thesis Case Western Reserve University Cleveland Ohio 1994.
  13. 10.1007/BF00121680 · doi:10.1007/bf00121680
  14. 10.1109/TC.2004.1255792 · doi:10.1109/tc.2004.1255792
  15. 10.1007/BF02238071 · doi:10.1007/bf02238071
  16. 10.1137/S0097539795283292 · doi:10.1137/s0097539795283292
  17. 10.1016/0166-218X(93)E0174-W · DOI
  18. 10.1287/opre.40.1.S28 · doi:10.1287/opre.40.1.s28
  19. 10.1089/cmb.2005.12.129 · doi:10.1089/cmb.2005.12.129
  20. J.Chuzhoy S.Guha S.Khanna J. S.Naor “Machine minimization for scheduling jobs with interval constraints” In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science Rome Italy 2004 pp.81–90. · doi:10.1109/focs.2004.38
  21. J.Chuzhoy J. S.Naor “New hardness results for congestion minimization and machine scheduling” In: Proceedings of the 36th ACM Symposium on the Theory of Computing Chicago Illinois 2004 pp.28–34. · doi:10.1145/1007352.1007364
  22. 10.1287/moor.1060.0218 · DOI
  23. M.Cieliebak T.Erlebach F.Hennecke B.Weber P.Widmayer “Scheduling with release times and deadlines on a minimum number of machines” In: Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science Toulouse France 2004 pp.217–230.
  24. 10.1002/nav.3800010309 · doi:10.1002/nav.3800010309
  25. 10.1287/opre.31.1.24 · doi:10.1287/opre.31.1.24
  26. 10.1287/opre.40.1.S76 · doi:10.1287/opre.40.1.s76
  27. 10.1016/0377-2217(93)90243-G · doi:10.1016/0377-2217(93)90243-g
  28. 10.1016/S0196-6774(02)00291-2 · doi:10.1016/s0196-6774(02)00291-2
  29. 10.1006/jagm.1998.1001 · doi:10.1006/jagm.1998.1001
  30. 10.1016/0166-218X(95)00112-5 · doi:10.1016/0166-218x(95)00112-5
  31. 10.1002/nav.10044 · doi:10.1002/nav.10044
  32. 10.1287/opre.35.6.849 · doi:10.1287/opre.35.6.849
  33. 10.1287/opre.37.3.395 · doi:10.1287/opre.37.3.395
  34. 10.1287/opre.40.1.S96 · DOI
  35. 10.1515/9781400875184 · DOI · Paper page
  36. 10.1016/0377-2217(95)00010-N · doi:10.1016/0377-2217(95)00010-n
  37. Garey M. R., 1979, Computers and intractability, a guide to the theory of NP‐completeness
  38. 10.1137/0601025 · doi:10.1137/0601025
  39. 10.1287/opre.26.1.68 · doi:10.1287/opre.26.1.68
  40. Golumbic M. C., 1980, Algorithmic graph theory and perfect graphs
  41. Graves S. C., 1993, Logistics of production and inventory
  42. 10.1109/TC.1979.1675260 · doi:10.1109/tc.1979.1675260
  43. 10.1006/jagm.1999.1060 · DOI
  44. 10.1287/opre.49.1.134.11192 · doi:10.1287/opre.49.1.134.11192
  45. A.Hashimoto J.Stevens Wire routing by optimizing channel assignment within large apertures Proceedings of the 8th Design Automation Workshop 1971 pp.155–169. · doi:10.1145/800158.805069
  46. Hochbaum D., 1997, Approximation algorithms for NP‐hard problems
  47. 10.1007/3-540-45032-7 · doi:10.1007/3-540-45032-7
  48. Ibaraki T., 1988, Resource allocation problems: Algorithmic approaches
  49. 10.1016/0377-2217(94)90150-3 · DOI
  50. 10.1006/jagm.1999.1022 · doi:10.1006/jagm.1999.1022
  51. 10.1016/0167-6377(92)90087-J · doi:10.1016/0167-6377(92)90087-j
  52. 10.1016/0377-2217(91)90320-U · doi:10.1016/0377-2217(91)90320-u
  53. 10.1016/0377-2217(93)90014-E · DOI
  54. 10.1016/0377-2217(94)90056-6 · doi:10.1016/0377-2217(94)90056-6
  55. Kolen A. W. J., 1995, Handbook of Combinatorics, 1875
  56. 10.1016/0377-2217(93)E0335-U · doi:10.1016/0377-2217(93)e0335-u
  57. 10.1287/opre.45.4.624 · doi:10.1287/opre.45.4.624
  58. Kroon L. G., 1996, Proceedings of the 22nd International Workshop on Graph‐Theoretic Concepts in Computer Science, 279
  59. 10.1007/BFb0053971 · doi:10.1007/bfb0053971
  60. R. J.Lipton A.Tomkins “Online interval scheduling” Proceedings of the fifth annual ACM‐SIAM Symposium on Discrete Algorithms Arlington Virginia 1994 pp.302–311.
  61. 10.1016/0377-2217(86)90016-0 · doi:10.1016/0377-2217(86)90016-0
  62. 10.1287/opre.47.6.873 · DOI
  63. 10.1023/B:JOSH.0000031423.39762.d3 · doi:10.1023/b:josh.0000031423.39762.d3
  64. 10.1016/0196-6774(82)90030-X · doi:10.1016/0196-6774(82)90030-x
  65. 10.1137/0211040 · doi:10.1137/0211040
  66. 10.1016/S0167-6377(98)00019-4 · DOI
  67. 10.1007/BFb0029570 · doi:10.1007/bfb0029570
  68. 10.1002/(SICI)1099-1425(199909/10)2:5<215::AID-JOS27>3.0.CO;2-Y · DOI
  69. Vazirani V. V., 2002, Approximation algorithms
  70. 10.1016/0304-3975(94)90150-3 · doi:10.1016/0304-3975(94)90150-3

Cited by

See all 220

Metadata

Authors
Kolen, A. W. J., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R.
Venue
Naval Research Logistics (NRL)
Publisher
Wiley
Published
2007-03-16
Volume
54
Issue
5
Pages
530-543
ISSN
  • 0894-069X (ISSN-L)
  • 1520-6750
DOI
10.1002/nav.20231
OpenAlex
W2110171203
Cited by
220
References
0
FWCI
18.11
Type
journal article
Language
en
Open access
bronze
Licence
onlinelibrary.wiley.com/termsAndConditions#vor (vor)

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Interval scheduling: A survey. https://app.cochat.ai/papers/10.1002/nav.20231
The paper
Kolen, A. W. J., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. Naval Research Logistics (NRL). https://doi.org/10.1002/nav.20231

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.