کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777196 | 1632576 | 2016 | 4 صفحه PDF | دانلود رایگان |
We consider the problem of scheduling parallel jobs on heterogeneous platforms. Given a set J of n jobs where each job jâ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 find a schedule for all jobs on the platforms minimizing the maximum completion time. The problem is directly related to a two-dimensional multi strip packing problem. 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 approximation algorithms. This closes the gap between the lower bound of <2 and the best approximation ratio.
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 9-12