The Allocation and Scheduling Precedence and Timing-Constrained Tasks with communication Delays

The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints is considered. A new heuristic with the time complexity of O(n2m), Least Space-Time First (LSTLP), is pro-posed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms. overhead subject to precedence and deadline constraints is considered. A new heuristic with the time complexity of O(n2m), Least Space-Time First (LSTLP), is pro-posed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.