TY - JOUR
T1 - An Improved Approximation for Scheduling Malleable Tasks with Precedence Constraints via Iterative Method
AU - Chen, Chi Yeh
N1 - Funding Information:
The work was supported by the Ministry of Science and Technology, Taiwan, R.O.C. under Grant no. MOST 106-2221-E-006-006.
Publisher Copyright:
© 1990-2012 IEEE.
PY - 2018/9/1
Y1 - 2018/9/1
N2 - The problem of scheduling malleable tasks with precedence constraints is one of the most important strongly NP-hard problems, given m identical processors and n tasks. A malleable task is one that runs in parallel on a varying number of processors. In addition, the processing sequences of tasks are constrained by the precedence constraints. The goal is to find a feasible schedule that minimizes the makespan (maximum completion time). This article presents an iterative method for improving the performance ratio of scheduling malleable tasks. The proposed algorithm achieves an approximation ratio of 4.4841 after 2 iterations. This improves the so far best-known factor of 4.7306 due to Jansen and Zhang. For a large number of iterations (>100), the approximation ratio of the proposed algorithm is tends toward 2+\sqrt2\approx 3.4143.
AB - The problem of scheduling malleable tasks with precedence constraints is one of the most important strongly NP-hard problems, given m identical processors and n tasks. A malleable task is one that runs in parallel on a varying number of processors. In addition, the processing sequences of tasks are constrained by the precedence constraints. The goal is to find a feasible schedule that minimizes the makespan (maximum completion time). This article presents an iterative method for improving the performance ratio of scheduling malleable tasks. The proposed algorithm achieves an approximation ratio of 4.4841 after 2 iterations. This improves the so far best-known factor of 4.7306 due to Jansen and Zhang. For a large number of iterations (>100), the approximation ratio of the proposed algorithm is tends toward 2+\sqrt2\approx 3.4143.
UR - http://www.scopus.com/inward/record.url?scp=85043790122&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043790122&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2018.2813387
DO - 10.1109/TPDS.2018.2813387
M3 - Article
AN - SCOPUS:85043790122
SN - 1045-9219
VL - 29
SP - 1937
EP - 1946
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 9
M1 - 8315149
ER -