LIP6 1997/027

• Habilitation «Algorithmes approchés pour des problèmes d'ordonnancement à temps de communication»
• A. Munier
• 53 pages - 11/12/1997 - document en - http://www.lip6.fr/lip6/reports/1997/lip6.1997.027.ps.tar.gz 2,592 Ko
• Contact Alix.Munier (at) nulllip6.fr
• Ancien Thème : SYSDEF
With the increasing importance of parallel computing, the question of how to schedule a set of tasks on an architecture becomes critical, and has received much attention. For the results toreflect modern architectures, communication delays between processors must be included in the model. Precedence relations between two tasks i and j expresses the fact that task j needs output of i to be executed. If these two tasks are not assigned to the same processor, a delay must be considered between the completion of i and the beginning of j to forward the data. The aim is to find a schedule that minimizes the makespan. These scheduling problems are difficult. This thesis is dedicated to the presentation of some ideas developed to get approximation algorithms to solve them. We show that linear programming and list scheduling are two efficient tools to get good approximation algorithms for general instances of these problems. We also point that duplication is a powerful way to get easier algorithms and good lower bounds.