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


Faigle, U. and Kern, W. and Nawijn, W.M. (1999) A greedy on-line algorithm for the k-track assignment problem. Journal of algorithms, 31 (1). pp. 196-210. ISSN 0196-6774

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Article
Copyright:© 1999 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74008
Official URL:https://doi.org/10.1006/jagm.1998.1001
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140560