Article ID: | iaor1999640 |
Country: | Netherlands |
Volume: | 94 |
Issue: | 2 |
Start Page Number: | 231 |
End Page Number: | 241 |
Publication Date: | Oct 1996 |
Journal: | European Journal of Operational Research |
Authors: | Liu Zhen, Blaewicz Jacek |
This paper is concerned with a new model in deterministic scheduling theory, where certain tasks may require more than one processor at a time. This model is motivated by several applications of multimicroprocessor systems and it has received much attention in the last years. In the paper it is assumed that each task can be processed on any processor subset of a given task-dependent size. Tasks are nonpreemptable and there are precedence constraints among them. It is proved that the problem of minimizing schedule length is NP-hard for three processors even if all the tasks have unit processing times and precedence constraints form a set of chains. Thus, it is unlikely to be solvable in polynomial time. On the other hand, two low order polynomial-time algorithms are given for the