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

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2018-09, Vol.29 (9), p.1937-1946
Main Author: Chen, Chi-Yeh
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Completion time
Heuristic algorithms
Iterative methods
Job shops
malleable tasks
Mathematical analysis
Precedence constraints
Processor scheduling
Processors
Production scheduling
Program processors
Schedules
Scheduling
Sequences
Task analysis
Task scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 + √2 ≈ 3.4143.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2018.2813387