Article ID: | iaor20052555 |
Country: | France |
Volume: | 34 |
Issue: | 2 |
Start Page Number: | 131 |
End Page Number: | 144 |
Publication Date: | Apr 2000 |
Journal: | RAIRO Operations Research |
Authors: | Guinand Frdric, Trystman Denis |
Keywords: | communication |
In this paper, we present a new linear time algorithm for scheduling UECT (Unit Execution and Communication Time) trees on two identical processors. The chosen criterion is the makespan. The used strategy is based on clustering of tasks. We show that this algorithm builds optimal schedules. Some extensions are discussed for non UECT tasks.