Rapport de Recherche Litp /
Litp research reports
19 pages - Février/February 1995 - Document en anglais.
PostScript : Ko /Kb
Titre / Title: An approximation algorithm for scheduling unitary tasks on m processors with communication delays
Abstract : This paper defines and studies a new list scheduling approximation algorithm for scheduling unitary tasks with unitary communication delays on m processors. In a first step, an approximated solution of the problem instance with an unlimited number of processors is generated. Then this solution is used to solve the resource conflicts during the list scheduling phase on m processors.
We prove that the relative performance of this algorithm can be bounded by 1+r-r/m, where r denotes the worst case performance of the solution generated in the first step. Then, we provide a polynomial algorithm with performance r=4/3 for the first step that leads to an overall worst case performance of 7/3-4/3m and we show that this bound is tight.
Publications internes Litp 1995 / Litp research reports 1995