Title :
Preemptable malleable task scheduling problem
Author :
Blazewicz, Jacek ; Kovalyov, Mikhail Y. ; Machowiak, Maciej ; Trystram, Denis ; Weglarz, Jan
Author_Institution :
Inst. of Comput. Sci., Poznan Tech. Univ., Poland
fDate :
4/1/2006 12:00:00 AM
Abstract :
The problem of optimal scheduling n independent malleable tasks in a parallel processor system is studied. It is assumed that an execution of any task can be preempted and the number of processors allocated to the same task can change during its execution. We present a rectangle packing algorithm, which converts an optimal solution for the relaxed problem, in which the number of processors allocated to a task is not required to be integer, into an optimal solution for the original problem in O(n) time.
Keywords :
computational complexity; processor scheduling; resource allocation; optimal scheduling; parallel processor system; preemptable malleable task scheduling problem; rectangle packing algorithm; Clustering algorithms; Concurrent computing; Costs; Large-scale systems; Multiprocessing systems; Optimal scheduling; Parallel processing; Processor scheduling; Resource management; Scheduling algorithm; Scheduling; parallel computing.; resource allocation;
Journal_Title :
Computers, IEEE Transactions on
