000K  utf8
1100  $c2015
1500  eng
2050  urn:nbn:de:gbv:8:1-zs-00000276-a8
3000  Jansen, Klaus
3010  Trystram, Denis
4000  Scheduling Parallel Jobs on a Network of Heterogeneous Platforms  [Jansen, Klaus]
4209  We consider the problem of scheduling parallel jobs on a network of heterogeneous platforms. Given a set J of n jobs where each job j 2 J is described by a pair (pj ; qj) with a processing time pj and number qj of processors required and a set of N heterogeneous platforms Pi with mi processors, the goal is to and a schedule for all jobs on the platforms minimizing the maximum completion time. Unless P = NP there is no approximation algorithm with absolute ratio better than 2 for the problem. We propose an approximation algorithm with absolute ratio 2 improving the previously best known algorithms. This closes the gap between the lower bound of 2 and the best approximation ratio.
4950  https://nbn-resolving.org/urn:nbn:de:gbv:8:1-zs-00000276-a8$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/macau_mods_00002007
5051  004