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

Research output: Contribution to journalArticlepeer-review

6 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

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'An Improved Approximation for Scheduling Malleable Tasks with Precedence Constraints via Iterative Method'. Together they form a unique fingerprint.

Cite this