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

被引：11

作者：

Chen, Chi-Yeh ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, 1 Univ Rd, Tainan 701, Taiwan

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2018年 / 29卷 / 09期

关键词：

Approximation algorithms; scheduling; malleable tasks; precedence constraints; PARALLEL TASKS; ALGORITHM; MULTIPROCESSORS; COMPLEXITY; GRAPHS;

D O I：

10.1109/TPDS.2018.2813387

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：1937 / 1946

页数：10

共 30 条

[1] Scheduling arbitrary number of malleable tasks on multiprocessor systems [J].

Barketau, M. S. ;

Kovalyov, M. Y. ;

Weglarz, J. ;

Machowiak, M. .

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES, 2014, 62 (02) :255-261

[2]

Blayo E, 1999, LECT NOTES COMPUT SC, V1685, P303

[3] Brief Announcement: Deadline-Aware Scheduling of Big-Data Processing Jobs [J].

Bodik, Peter ;

Menache, Ishai ;

Naor, Joseph ;

Yaniv, Jonathan .

PROCEEDINGS OF THE 26TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA'14), 2014, :211-213

[4]

Caron E, 2016, 2016 2ND INTERNATIONAL CONFERENCE ON CLOUD COMPUTING TECHNOLOGIES AND APPLICATIONS (CLOUDTECH), P326, DOI 10.1109/CloudTech.2016.7847717

[5] SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets [J].