DEADLINE SCHEDULING OF MULTIPROCESSOR TASKS

In the classical scheduling theory it is widely assumed that any task requires for its processing only one processor at a time. Nowadays wit h the technological progress this assumption has become not so obvious . In the paper, two algorithms for solving the problem of scheduling t asks requiring more than one processor at a time in the real-time envi ronment, will be given. The first is based on a generation of all feas ible layouts of tasks and on an application of linear programming. The second - heuristic one - is based on the descent search in solution s pace and the tabu search metaheuristic combined with linear programmin g. Results of a computational comparison of the two methods, are also reported.