Fixed interval scheduling: Models, applications, computational complexity and algorithms

Mikhail Y. Kovalyov, Chi To Ng, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

109 Citations (Scopus)

Abstract

The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.
Original languageEnglish
Pages (from-to)331-342
Number of pages12
JournalEuropean Journal of Operational Research
Volume178
Issue number2
DOIs
Publication statusPublished - 16 Apr 2007

Keywords

  • Discrete starting times
  • Interval graph
  • Interval scheduling
  • k-coloring
  • k-track assignment
  • Maximum weight clique
  • Maximum weight independent set

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this