Note on scheduling intervals on-line

U. Faigle, W.M. Nawijn

Research output: Contribution to journalArticleAcademicpeer-review

61 Citations (Scopus)
250 Downloads (Pure)


An optimal on-line algorithm is presented for the following optimization problem, which constitutes the special case of the k-track assignment problem with identical time windows. Intervals arrive at times ti and demand service time equal to their length. An interval is considered lost if it is not assigned to one of k identical service stations immediately or if its service is interrupted. Minimizing the losses amounts to coloring a maximal set of intervals in the associated interval graph properly with at most k colors. Optimality of the on-line algorithm is proved by showing that it performs as well as the optimal greedy k-coloring algorithm due to Faigle and Nawijn and, independently, to Carlisle and Lloyd for the same problem under full a priori information.
Original languageEnglish
Pages (from-to)13-17
Number of pages5
JournalDiscrete applied mathematics
Issue number1
Publication statusPublished - 1995


Dive into the research topics of 'Note on scheduling intervals on-line'. Together they form a unique fingerprint.

Cite this