An approximation algorithm for scheduling dependent tasks on m processors with small communication delays

This paper defines and studies an approximation algorithm for scheduling ta sks with small communication delays on in processors starting from a schedu le sigma (infinity) for the problem instance with an unlimited number of pr ocessors with relative performance bounded by alpha. This solution is used to solve the resource conflicts during the scheduling phase on m processors . A mechanism for UET-UCT tasks systems is first presented and analyzed. Th en a rather unusual feature is introduced to handle SCT task systems: a pro cessor 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)alpha. If the best-kn own ratio alpha = 4/3 is used it induces a worst-case performance bounded b y 7/3 - 4/m for our algorithm. (C) 2001 Elsevier Science B.V. All rights re served. MSC 68M20.