Highly Constrained Task Scheduling on Multiprocessing Systems

The problem of non-preemptively scheduling a set of m tasks on n processors
with communication overhead subject to precedence, memory and deadline
constraints is considered. A new heuristic with the time complexity of 0(m2n),
Augmented Least Space-Time First (LSTF), is proposed to minimize the maximum
tardiness. The efficiency of the augmented LSTF using a large number of
randomly-generated graphs and three real-world structures is compared with that of
the augmented Earliest Deadline First- Earliest Task First (EDF-E) that schedules
each ready task on the processor at which it can be scheduled at the earliest time
and with that of EDF-R that select the processor at random. The result of the
comparisons, which are based on the maximum tardiness and the number of tasks
that miss their deadlines, indicates that the augmented LSTF outperforms both
EDF-E and EDF-R.