Scheduling multiprocessor tasks with chain constraints

Scheduling multiprocessor tasks with chain constraints

0.00 Avg rating0 Votes
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: ,
Abstract:

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 m processor case if processor requirements of the tasks in each chain are either uniform or monotonically decreasing (increasing).

Reviews

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