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

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.