A Greedy On-Line Algorithm for thek-Track Assignment Problem

✍ Scribed by U Faigle; W Kern; W.M Nawijn

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 107 KB
• Volume: 31
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.1001

✦ Synopsis

Given a collection I I 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 s 1, our bound implies that our algorithm loses at most k y 1 jobs relative to the optimum. We show by an explicit construction that the bound is tight for greedy on-line algorithms.