Jansen, Klaus and Zhang, H. (2012) Scheduling malleable tasks with precedence constraints. Journal of Computer and System Sciences, 78 (1). pp. 245-259.

Full text not available from this repository.

Abstract

In this paper we propose an approximation algorithm for scheduling malleable tasks with precedence constraints. Based on an interesting model for malleable tasks with continuous processor allotments by Prasanna and Musicus (1991. 1994, 1996) vertical bar 23-25 vertical bar, we define two natural assumptions for malleable tasks: the processing time of any malleable task is non-increasing in the number of processors allotted, and the speedup is concave in the number of processors. We show that under these assumptions the work function of any malleable task is non-decreasing in the number of processors and is convex in the processing time. Furthermore, we propose a two-phase approximation algorithm for the scheduling problem. In the first phase we solve a linear program to obtain a fractional allotment for all tasks. By rounding the fractional solution, each malleable task is assigned a number of processors. In the second phase a variant of the list scheduling algorithm is employed. By choosing appropriate values of the parameters, we show (via a nonlinear program) that the approximation ratio of our algorithm is at most 100/63 + 100(root 6469 + 13)/5481 approximate to 3.291919. We also show that our result is asymptotically tight. (C) 2011 Elsevier Inc. All rights reserved.

Document Type:	Article
Additional Information:	RBC Financial Grp, Toronto, ON M5J 2J5, Canada. Univ Kiel, Inst Comp Sci & Appl Math, D-24098 Kiel, Germany. Zhang, H (reprint author), RBC Financial Grp, 200 Bay St,Royal Bank Plaza,11th Floor,South Towe, Toronto, ON M5J 2J5, Canada. kj@informatik.uni-kiel.de; hu.zhang@rbccm.com
Keywords:	Approximation algorithm Scheduling Malleable tasks approximation algorithms parallel tasks graphs model logp
Research affiliation:	OceanRep > The Future Ocean - Cluster of Excellence
Projects:	Future Ocean
Date Deposited:	14 May 2014 09:59
Last Modified:	14 May 2014 09:59
URI:	https://oceanrep.geomar.de/id/eprint/24052

Actions (login required)

View Item