L. Bianco et al., LINEAR ALGORITHMS FOR PREEMPTIVE SCHEDULING OF MULTIPROCESSOR TASKS SUBJECT TO MINIMAL LATENESS, Discrete applied mathematics, 72(1-2), 1997, pp. 25-46
In scheduling theory it is widely assumed that a task is to be process
ed on one processor at a time. This assumption is not so obvious in th
e context of recently emerging parallel computer systems and parallel
algorithms. In this work we consider tasks requiring more than one ded
icated processor at a time, i.e. sets of processors simultaneously. Li
near time algorithms will be given for the case of two, three and four
processors and the L(max) criterion. The algorithms are based on the
same simple paradigm. In some cases they deliver optimal solutions. In
other cases, optimality is not guaranteed but they can still be used
as fast approximation algorithms for which the worst case performance
bounds are given. Results of the computational experiments involving f
our processors are reported.