کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439353 690530 2006 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A -approximation algorithm for scheduling identical malleable tasks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A -approximation algorithm for scheduling identical malleable tasks
چکیده انگلیسی

We consider the problem of finding a schedule for n-independent identical malleable tasks on p identical processors with minimal completion time. This problem arises while using the branch-and-bound or the divide-and-conquer strategy to solve a problem on a parallel system. If nothing is known about the subproblems, then they are assumed to be identical. We assume that the execution time decreases with the number of processors while the computational work increases. We give an algorithm with execution time exponential in p which computes an optimal schedule. In order to approximate an optimal schedule, we use the concept of phase-by-phase schedules. Here schedules consist of phases in which every job uses the same number of processors. We prove that one can approximate an optimal schedule up to a factor of using constant time, and we show that this is optimal. Furthermore, we give an ε-approximation algorithm if the speed-up is optimal up to a constant factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 361, Issues 2–3, 1 September 2006, Pages 226-240