A greedy on-line algorithm for the k-track assignment problem

U. Faigle, Walter Kern, W.M. Nawijn

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

Abstract

Given a collection [.] of n jobs that are represented by intervals, we seek a maximal feasible assignment of the jobs to k machines such that not more than c(M) intervals overlap pairwise on any machine M and that a job is only assigned to a machine if it fits into one of several prescribed time windows for that machine. We analyze an on-line version of this NP-complete problem and exhibit an algorithm that achieves at least half of the (theoretical) optimum. In a more detailed analysis, we bound the performance of our algorithm by an additive term that only depends on the time window structure of the machines (but not on the number of jobs). In the case where each machine M has capacity c(M) = 1, our bound implies that our algorithm loses at mostk − 1 jobs relative to the optimum. We show by an explicit construction that the bound is tight for greedy on-line algorithms.
Original languageUndefined
Pages (from-to)196-210
Number of pages15
JournalJournal of algorithms
Volume31
Issue number1
DOIs
Publication statusPublished - 1999

Keywords

  • Scheduling
  • Online
  • time window
  • METIS-140560
  • Greedy algorithm
  • Interval order
  • IR-74008
  • k-track assignment

Cite this