The allocation and scheduling of precedence- and timing-constrained tasks with communication delays
Bo‐Chao Cheng, Alexander D. Stoyenko, Thomas J. Marlowe, Sanjoy Baruah · 2002
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(n/sup 2/m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.