Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors |
| |
| Institution: | 1. Systems Research Institute, Polish Academy of Sciences, Newelska 6, Warsaw 01-447, Poland;2. The International University of Logistics and Transport in Wroc?aw, So?tysowicka St. 19B, Wroc?aw 51-168, Poland;1. Centro de Matemática Aplicações Fundamentais e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, Lisboa, 1749-016, Portugal;2. ABB Corporate Research, Wallstadter Strasse 59, Ladenburg, 68526, Baden-Württemberg, Germany;3. Center for Advanced Process Decision-Making, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
