An Improved Approximation for Scheduling Malleable Tasks with Precedence Constraints via Iterative Method

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number8315149
Pages (from-to)1937-1946
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Volume29
Issue number9
DOIs
Publication statusPublished - 2018 Sep 1

Fingerprint

Iterative methods
Scheduling
Computational complexity
Processing

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{7e60b0c7eb584bb1a725bdf341c2dc41,
title = "An Improved Approximation for Scheduling Malleable Tasks with Precedence Constraints via Iterative Method",
abstract = "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.",
author = "Chen, {Chi Yeh}",
year = "2018",
month = "9",
day = "1",
doi = "10.1109/TPDS.2018.2813387",
language = "English",
volume = "29",
pages = "1937--1946",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "9",

}

TY - JOUR

T1 - An Improved Approximation for Scheduling Malleable Tasks with Precedence Constraints via Iterative Method

AU - Chen, Chi Yeh

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

VL - 29

SP - 1937

EP - 1946

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 9

M1 - 8315149

ER -