Scheduling malleable tasks with precedence constraints

作者:

Highlights:

摘要

In this paper we propose an approximation algorithm for scheduling malleable tasks with precedence constraints. Based on an interesting model for malleable tasks with continuous processor allotments by Prasanna and Musicus (1991, 1994, 1996) [23], [24], [25], we define two natural assumptions for malleable tasks: the processing time of any malleable task is non-increasing in the number of processors allotted, and the speedup is concave in the number of processors. We show that under these assumptions the work function of any malleable task is non-decreasing in the number of processors and is convex in the processing time. Furthermore, we propose a two-phase approximation algorithm for the scheduling problem. In the first phase we solve a linear program to obtain a fractional allotment for all tasks. By rounding the fractional solution, each malleable task is assigned a number of processors. In the second phase a variant of the list scheduling algorithm is employed. By choosing appropriate values of the parameters, we show (via a nonlinear program) that the approximation ratio of our algorithm is at most 100/63+100(6469+13)/5481≈3.291919. We also show that our result is asymptotically tight.

论文关键词:Approximation algorithm,Scheduling,Malleable tasks

论文评审过程:Received 5 May 2006, Revised 26 March 2009, Accepted 8 April 2011, Available online 22 April 2011.

论文官网地址:https://doi.org/10.1016/j.jcss.2011.04.003