000K  utf8
1100  $c2013
1500  eng
2050  urn:nbn:de:101:1-201303157479
3000  Dutot, Pierre-Francois
3010  Jansen, Klaus
3010  Robenek, Christina
3010  Trystram, Denis
4000  A (2+ɛ)-approximation for scheduling parallel jobs in platforms  [Dutot, Pierre-Francois]
4209  We consider the problem of \textsc{Scheduling parallel Jobs in heterogeneous Platforms}: We are given a set $\mathcal{J}=\{1,\ldots,n\}$ of $n$ jobs, where a job $j\in\mathcal{J}$ is described by a pair $(p_j,q_j)$ of a processing time $p_j\in\mathbb{Q}_{>0}$ and the number of processors $q_j\in\mathbb{N}$ that are required to execute $j$. We are also given a set $\mathcal{B}$ of $N$ heterogeneous platforms $P_1,\ldots,P_N$, where each $P_i$ contains $m_{i}$ processors for $i\in\{1,\ldots, N\}.$ The objective is to find a schedule for the jobs in the platforms minimizing the makespan, i.e. the latest finishing time of a job. Unless $\mathcal{P}=\mathcal{NP}$ there is no approximation algorithm with absolute ratio strictly better than $2$ for the problem. We give a $(2+\epsilon)$-approximation for the problem improving the previously best known absolute approximation ratio $3$.
4950  https://nbn-resolving.org/urn:nbn:de:101:1-201303157479$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/macau_mods_00001794
5051  004