Annals of Operations Research. 129(1-2-3-4):65–80, JULY 2004

Issn Print: 0254-5330

Publication Date: July 2004

# Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan*

Jacek Błażewicz;Maciej Machowiak;Jan Węglarz;Mikhail Kovalyov;Denis Trystram;

+ Author Information

1Instytut Informatyki, Politechnika Poznanska, ul. Piotrowo 3, 60-965 Poznan, Poland2Faculty of Economics, Belarus State University, Minsk, Belarus3Laboratory Informatique et Distribution, IMAG, Grenoble, France

### Abstract

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n ≤ m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(n max{m, n log2m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n = 2 or n = 3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.