TY - JOUR

T1 - A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints

AU - Chen, Chi Yeh

AU - Chu, Chih Ping

PY - 2013/7/17

Y1 - 2013/7/17

N2 - Scheduling malleable tasks under general precedence constraints involves finding a minimum makespan (maximum completion time) by a feasible allotment. Based on the monotonous penalty assumptions of Blayo et al. [2], this work defines two assumptions concerning malleable tasks: the processing time of a malleable task is nonincreasing in the number of processors, while the work of a malleable task is nondecreasing in the number of processors. Additionally, the work function is assumed herein to be convex in the processing time. The proposed algorithm reformulates the linear program of [11], and this algorithm and associated proofs are inspired by the ones of [11]. This work describes a novel polynomial-time approximation algorithm that is capable of achieving an approximation ratio of 2+√2 ∼ 3.4142. This work further demonstrates that the proposed algorithm can yield an approximation ratio of 2.9549 when the processing time is strictly decreasing in the number of the processors allocated to the task. This finding represents an improvement upon the previous best approximation ratio of 100/63+100(√6469+137)/5481 ∼ 3.2920) [12] achieved under the same assumptions.

AB - Scheduling malleable tasks under general precedence constraints involves finding a minimum makespan (maximum completion time) by a feasible allotment. Based on the monotonous penalty assumptions of Blayo et al. [2], this work defines two assumptions concerning malleable tasks: the processing time of a malleable task is nonincreasing in the number of processors, while the work of a malleable task is nondecreasing in the number of processors. Additionally, the work function is assumed herein to be convex in the processing time. The proposed algorithm reformulates the linear program of [11], and this algorithm and associated proofs are inspired by the ones of [11]. This work describes a novel polynomial-time approximation algorithm that is capable of achieving an approximation ratio of 2+√2 ∼ 3.4142. This work further demonstrates that the proposed algorithm can yield an approximation ratio of 2.9549 when the processing time is strictly decreasing in the number of the processors allocated to the task. This finding represents an improvement upon the previous best approximation ratio of 100/63+100(√6469+137)/5481 ∼ 3.2920) [12] achieved under the same assumptions.

UR - http://www.scopus.com/inward/record.url?scp=84880050231&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880050231&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2012.258

DO - 10.1109/TPDS.2012.258

M3 - Article

AN - SCOPUS:84880050231

VL - 24

SP - 1479

EP - 1488

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 8

M1 - 6295609

ER -