Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors

Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors

0.00 Avg rating0 Votes
Article ID: iaor1999641
Country: Netherlands
Volume: 94
Issue: 2
Start Page Number: 242
End Page Number: 251
Publication Date: Oct 1996
Journal: European Journal of Operational Research
Authors:
Abstract:

This paper investigates the computational complexity of preemptive and nonpreemptive scheduling of biprocessor tasks on dedicated processors in general and some of its special cases. We consider two criteria of optimality: the schedule length and sum of task completion times. In addition, we analyze the complexity of these problems when precedence constraints are involved. We show that in general all these problems are NP-hard in the strong sense.

Reviews

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