Name
Abstract | ||
|---|---|---|
We consider the Multiple Cluster Scheduling Problem (MCSP), where the objective is to schedule n parallel rigid jobs on N identical clusters, minimizing the maximum completion time (make span). MCSP is 2-inapproximable (unless P=NP), and several approximation algorithms have already been proposed. However, ratio 2 has only been reached by algorithms that use extremely costly and complex subroutines as "black boxes" which are polynomial and yet impractical due to prohibitive constants. Our objective within this work is to determine a reasonable restriction of MCSP where the in approximability lower bound could be tightened in almost linear time. Thus, we consider a restriction of MCSP where jobs do not require strictly more than half of the processors of a cluster, and we provide a 2-approximation running in O(log(nh_{max})n(N+log(n))), where h_{max} is the processing time of the longest job. This approximation is the best possible, as this restriction (and even simpler ones) remains 2-inapproximable. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/IPDPSW.2012.108 | IPDPS Workshops |
Keywords | Field | DocType |
identical clusters,processing time,n identical cluster,parallel jobs,maximum completion time,2-approximation running,tight approximation,complex subroutine,approximation algorithm,reasonable restriction,linear time,black box,multiple cluster scheduling problem,strips,schedules,approximation algorithms,minimisation,parallel processing,scheduling,silicon,black boxes,computational complexity,approximation theory,clustering algorithms | Approximation algorithm,Job shop scheduling,Polynomial,Computer science,Upper and lower bounds,Parallel computing,Approximation theory,Schedule,Time complexity,Computational complexity theory,Distributed computing | Conference |
ISSN | Citations | PageRank |
2164-7062 | 2 | 0.40 |
References | Authors | |
5 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marin Bougeret | 1 | 113 | 13.35 |
| Pierre-françois Dutot | 2 | 166 | 13.95 |
| Klaus Jansen | 3 | 2 | 0.40 |
| Christina Robenek | 4 | 23 | 2.58 |
| Denis Trystram | 5 | 1120 | 160.57 |