An approximation algorithm for scheduling dependent tasks on m processors with small communication delays
This paper defines and studies an approximation algorithm for scheduling tasks with small communication delays on m processors starting from a schedule ?? for the problem instance with an unlimited number of processors with relative performance bounded by ?. This solution is used to solve the resource conflicts during the scheduling phase on m processors. A mechanism for UETUCT tasks systems is first presented and analyzed. Then a rather unusual feature is introduced to handle SCT task systems: a processor may remain idle even if some tasks are feasible in order to wait for a more important task. The schedule generated by this algorithm is proved to have an overall worst-case performance 1+(1?1/m)?. If the best-known ratio is used it induces a worst-case performance bounded by for our algorithm.
68m20