Scheduling multiprocessor tasks for mean flow time criterion

Scheduling multiprocessor tasks for mean flow time criterion

0.00 Avg rating0 Votes
Article ID: iaor2001563
Country: United Kingdom
Volume: 27
Issue: 6
Start Page Number: 571
End Page Number: 585
Publication Date: May 2000
Journal: Computers and Operations Research
Authors: ,
Keywords: scheduling, computational analysis: parallel computers, heuristics
Abstract:

Multiprocessor tasks are executed by more than one processor at the same moment of time. This work considers the problem of scheduling unit execution-time and preemptable multiprocessor tasks on m parallel identical processors to minimize mean flow time and mean weighted flow time. We analyze complexity status of the problem. When tasks have unit execution time and the number of processors is arbitrary the problem is shown to be computationally hard. Constructing an optimal preemptive schedule is also computationally hard in general. Polynomial algorithms are presented for scheduling unit execution time tasks when the number of processors is fixed, or the numbers of simultaneously required processors are powers of 2. The case of preemptable tasks requiring either 1 or m processors simultaneously is solvable in low-order polynomial time.

Reviews

Required fields are marked *. Your email address will not be published.