Name
Abstract | ||
|---|---|---|
We present in this article a new approximation algorithm for scheduling a set of n independent rigid (meaning requiring a fixed number of processors) jobs on hierarchical parallel computing platform. A hierarchical parallel platform is a collection of k parallel machines of different sizes (number of processors). The jobs are submitted to a central queue and each job must be allocated to one of the k parallel machines (and then scheduled on some processors of this machine), targeting theminimization of the maximum completion time (makespan). We assume that no job require more resources than available on the smallest machine. This problem is hard and it has been previously shown that there is no polynomial approximation algorithm with a ratio lower than 2 unless P = NP. The proposed scheduling algorithm achieves a 5/2 ratio and runs in O(log(npmax)knlog(n)), where pmax is the maximum processing time of the jobs. Our results also apply for the Multi Strip Packing problem where the jobs (rectangles) must be allocated on contiguous processors. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-15277-1_16 | Euro-Par (1) |
Keywords | Field | DocType |
hierarchical parallel platform,multi strip packing problem,k parallel machine,polynomial approximation algorithm,maximum processing time,maximum completion time,2-approximation algorithm,hierarchical scheduling,hierarchical parallel computing platform,new approximation algorithm,fixed number,proposed scheduling algorithm,approximation algorithm,scheduling,parallel computer,scheduling algorithm | Approximation algorithm,Job shop scheduling,Multiprocessor scheduling,Polynomial,Fair-share scheduling,Scheduling (computing),Computer science,Queue,Parallel computing,Strip packing problem,Distributed computing | Conference |
Volume | ISSN | ISBN |
6271 | 0302-9743 | 3-642-15276-7 |
Citations | PageRank | References |
10 | 0.51 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marin Bougeret | 1 | 113 | 13.35 |
| Pierre-françois Dutot | 2 | 166 | 13.95 |
| Klaus Jansen | 3 | 34 | 3.21 |
| Christina Otte | 4 | 17 | 1.05 |
| Denis Trystram | 5 | 1120 | 160.57 |