G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-spaccamela et al., Complexity and Approximation, 1999.

M. Banikazemi, V. Moorthy, and D. K. Panda, Efficient collective communication on heterogeneous networks of workstations, Proceedings of the 27th International Conference on Parallel Processing (ICPP'98), 1998.

M. Banikazemi, J. Sampathkumar, S. Prabhu, D. K. Panda, and P. Sadayappan, Communication modeling of heterogeneous networks of workstations for performance characterization of collective operations, HCW'99, the 8th Heterogeneous Computing Workshop, pp.125-133, 1999.

C. Banino, O. Beaumont, A. Legrand, and Y. Robert, Scheduling strategies for master-slave tasking on heterogeneous processor grids, PARA'02: International Conference on Applied Parallel Computing, vol.2367, pp.423-432, 2002.
URL : https://hal.archives-ouvertes.fr/hal-00807406

O. Beaumont, V. Boudet, and Y. Robert, A realistic model and an efficient heuristic for scheduling with heterogeneous processors, HCW'2002, the 11th Heterogeneous Computing Workshop, 2002.
URL : https://hal.archives-ouvertes.fr/hal-00807411

O. Beaumont, L. Carter, J. Ferrante, A. Legrand, and Y. Robert, Bandwidth-centric allocation of independent tasks on heterogeneous platforms, International Parallel and Distributed Processing Symposium (IPDPS'2002), 2002.
URL : https://hal.archives-ouvertes.fr/inria-00072412

O. Beaumont, A. Legrand, L. Marchal, and Y. Robert, Complexity results and heuristics for pipelined multicast operations on heterogeneous platforms, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00789448

O. Beaumont, A. Legrand, L. Marchal, and Y. Robert, Pipelining broadcasts on heterogeneous platforms, International Parallel and Distributed Processing Symposium IPDPS, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00358950

D. Bertsimas and D. Gamarnik, Asymptotically optimal algorithm for job shop scheduling and packet routing, Journal of Algorithms, vol.33, issue.2, pp.296-318, 1999.

M. D. Beynon, T. Kurc, A. Sussman, and J. Saltz, Optimizing execution of componentbased applications using group instances, Future Generation Computer Systems, vol.18, issue.4, pp.435-448, 2002.

P. B. Bhat, V. K. Prasanna, and C. S. Raghavendra, Efficient collective communication in distributed heterogeneous systems, 19th IEEE International Conference on Distributed Computing Systems (ICDCS'99), 1999.

V. Boudet and Y. Robert, Scheduling heuristics for heterogeneous processors, International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'2001), pp.2109-2115, 2001.
URL : https://hal.archives-ouvertes.fr/hal-00808290

P. Boulet, J. Dongarra, F. Rastello, Y. Robert, and F. Vivien, Algorithmic issues on heterogeneous computing platforms. Parallel Processing Letters, vol.9, issue.2, pp.197-213, 1999.

T. D. Braun, H. J. Siegel, and N. Beck, Optimal use of mixed task and data parallelism for pipelined computations, J. Parallel and Distributed Computing, vol.61, pp.810-837, 2001.

L. Carter, H. Casanova, J. Ferrante, and B. Kreaseck, Autonomous protocols for bandwidth-centric scheduling of independent-task applications, International Parallel and Distributed Processing Symposium IPDPS, 2003.

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, 1990.

G. H. Golub and C. F. Van-loan, Matrix computations. Johns Hopkins, 1989.

J. Goux, S. Kulkarni, J. Linderoth, and M. Yoder, An enabling framework for master-worker applications on the computational grid, Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00), 2000.

N. G. Hall, W. Liu, and J. B. Sidney, Scheduling in broadcast networks, Networks, vol.32, issue.14, pp.233-253, 1998.

J. Hatta and S. Shibusawa, Scheduling algorithms for efficient gather operations in distributed heterogeneous systems, 2000 International Conference on Parallel Processing, 2000.

E. Heymann, M. A. Senar, E. Luque, and M. Livny, Adaptive scheduling for master-worker applications on the computational grid, Grid Computing -GRID 2000, pp.214-227, 1971.

L. Hollermann, T. S. Hsu, D. R. Lopez, and K. Vertanen, Scheduling problems in a practical allocation model, J. Combinatorial Optimization, vol.1, issue.2, pp.129-149, 1997.

B. Hong and V. K. Prasanna, Bandwidth-aware resource allocation for heterogeneous computing systems to maximize throughput, Proceedings of the 32th International Conference on Parallel Processing, 2003.

T. S. Hsu, J. C. Lee, D. R. Lopez, and W. A. Royce, Task allocation on a network of processors, IEEE Trans. Computers, vol.49, issue.12, pp.1339-1353, 2000.

S. L. Johnsson and C. Ho, Optimum broadcasting and personalized communication in hypercubes, IEEE Trans. Computers, vol.38, issue.9, pp.1249-1268, 1989.

D. W. Krumme, G. Cybenko, and K. N. Venkataraman, Gossiping in minimal time, SIAM J. Computing, vol.21, pp.111-139, 1992.

A. Legrand, L. Marchal, and Y. Robert, Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms, APDCM'2004, 6th Workshop on Advances in Parallel and Distributed Computational Models, 2004.
URL : https://hal.archives-ouvertes.fr/hal-02101968

R. Libeskind-hadas, J. R. Hartline, P. Boothe, G. Rae, and J. Swisher, On multicast algorithms for heterogeneous networks of workstations, Journal of Parallel and Distributed Computing, vol.61, issue.11, pp.1665-1679, 2001.

P. Liu, Broadcast scheduling optimization for heterogeneous cluster systems, Journal of Algorithms, vol.42, issue.1, pp.135-152, 2002.

P. Liu and T. Sheng, Broadcast scheduling optimization for heterogeneous cluster systems, SPAA'2000, 12th Annual ACM Symposium on Parallel Algorithms and Architectures, p.5198, 2000.

M. Maheswaran and H. J. Siegel, A dynamic matching and scheduling algorithm for heterogeneous computing systems, Seventh Heterogeneous Computing Workshop, 1998.

H. Oh and S. Ha, A static scheduling heuristic for heterogeneous processors, Proceedings of Europar'96, vol.1123, 1996.

A. Schrijver, Theory of Linear and Integer Programming, 1986.

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol.24, 2003.

G. Shao, Adaptive scheduling of master/worker applications on distributed computational resources, 2001.

G. Shao, F. Berman, and R. Wolski, Master/slave computing on the grid, Heterogeneous Computing Workshop HCW'00, 2000.

B. A. Shirazi, A. R. Hurson, and K. M. Kavi, Scheduling and load balancing in parallel and distributed systems, 1995.

G. C. Sih and E. A. Lee, A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE Transactions on Parallel and Distributed Systems, vol.4, issue.2, pp.175-187, 1993.

O. Sinnen and L. Sousa, Comparison of contention-aware list scheduling heuristics for cluster computing, Workshop for Scheduling and Resource Management for Cluster Computing (ICPP'01), pp.382-387, 2001.

O. Sinnen and L. Sousa, Exploiting unused time-slots in list scheduling considering communication contention, EuroPar'2001 Parallel Processing, pp.166-170, 2001.

M. Spencer, R. Ferreira, M. Beynon, T. Kurc, U. Catalyurek et al., Executing multiple pipelined data analysis operations in the grid, 2002 ACM/IEEE Supercomputing Conference, 2002.

K. Taura and A. A. Chien, A heuristic algorithm for mapping communicating tasks on heterogeneous resources, Heterogeneous Computing Workshop, pp.102-115, 2000.

H. Topcuoglu, S. Hariri, and M. Wu, Task scheduling algorithms for heterogeneous processors, Eighth Heterogeneous Computing Workshop, 1999.

J. B. Weissman, Scheduling multi-component applications in heterogeneous wide-area networks, Heterogeneous Computing Workshop HCW'00, 2000.

. Unité-de-recherche-inria-futurs, Parc Club Orsay Université -ZAC des Vignes 4, rue Jacques Monod -91893 ORSAY Cedex

. Unité-de-recherche-inria-lorraine, LORIA, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602