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: | Kubale Marek |
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.