Journal
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume 29, Issue 9, Pages 1937-1946Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2018.2813387
Keywords
Approximation algorithms; scheduling; malleable tasks; precedence constraints
Funding
- Ministry of Science and Technology, Taiwan, R.O.C. [MOST 106-2221-E-006-006]
Ask authors/readers for more resources
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 +root 2 approximate to 3.4143.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available