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

Given a collection Fz 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 onl y assigned to a machine if it fits into one of several prescribed time wind ows for that machine. We analyze an on-line version of this NP-complete pro blem and exhibit an algorithm that achieves at least half of the (theoretic al) optimum. In a more detailed analysis, we bound the performance of our a lgorithm 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 ma chine M has capacity c(M) = 1, our bound implies that our algorithm loses a t most k - 1 jobs relative to the optimum. We show by an explicit construct ion that the bound is tight for greedy on-line algorithms. (C) 1999 Academi c Press.