Name
Abstract | ||
|---|---|---|
We consider the problem of scheduling n intervals (jobs with fixed starting times) on m machines with different speeds with the objective to maximize the number of accepted intervals. We prove that the offline version of the problem is strongly NP-hard to solve. For the online version, we show a lower bound of 53 on the competitive ratio of any deterministic online algorithm for the problem. Moreover, we present two simple greedy rules for online algorithms and show that any online algorithm using these rules is 2-competitive. One of these 2-competitive algorithms is shown to run in O(nlogm) time. Additionally, we prove that our greedy rules impose no loss in the sense that every online algorithm for the problem can be modified to use the rules without reducing the number of accepted intervals on any instance. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.cor.2011.03.001 | Computers & OR |
Keywords | DocType | Volume |
Computational complexity,greedy rule,competitive ratio,offline version,accepted interval,2-competitive algorithm,related machine,interval scheduling,online algorithm,Scheduling,online version,Online algorithms,deterministic online algorithm,Competitive analysis,different speed,simple greedy rule | Journal | 38 |
Issue | ISSN | Citations |
12 | Computers and Operations Research | 5 |
PageRank | References | Authors |
0.49 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Clemens Thielen | 2 | 75 | 15.11 |
| Stephan Westphal | 3 | 97 | 13.41 |