Name
Abstract | ||
|---|---|---|
The Multiple Cluster Scheduling Problem corresponds to minimizing the maximum completion time (makespan) of a set of n parallel rigid (and non-preemptive) jobs submitted to N identical clusters. It cannot be approximated with a ratio better than 2 (unless P = NP ). We present in this paper the methodology that encompasses several existing results 1,2. We detail first how to apply it for obtaining a 5 2 -approximation. Then, we use it to provide a new 7 3 -approximation running in O ( log ¿ ( n h max ) N ( n + log ¿ ( n ) ) ) , where h max is the processing time of the longest job. Finally, we apply it to a restriction of the problem to jobs of limited size, leading to a 2-approximation which is the best possible ratio since the restriction remains 2-inapproximable. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.07.003 | Theoretical Computer Science |
Keywords | Field | DocType |
Scheduling,Parallel job,Strip packing,Approximation algorithm | Discrete mathematics,Cluster (physics),Approximation algorithm,Combinatorics,Job shop scheduling,Scheduling (computing),Strip packing,Mathematics | Journal |
Volume | Issue | ISSN |
600 | C | 0304-3975 |
Citations | PageRank | References |
3 | 0.41 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marin Bougeret | 1 | 113 | 13.35 |
| Pierre-françois Dutot | 2 | 166 | 13.95 |
| Denis Trystram | 3 | 1120 | 160.57 |
| Klaus Jansen | 4 | 34 | 3.21 |
| Christina Robenek | 5 | 23 | 2.58 |