UET-UCT Schedules on Arbitrary Networks C. PICOULEAU De nombreux résultats de complexité pour les problèmes d'ordonnancement avec délais de communication ont récemment été prouvés. Pour ces problèmes, il est supposé que le réseau de pro­ cesseurs est entièrement connecté. Dans cet article, le réseau de processeurs n'est pas nécessairement entièrement connecté, et les délais de communication dépendent de la distance entre les pro­ cesseurs. Nous définissons 'UET-UCT-topo' une nouvelle classe de problèmes d'ordonnancement : les durées d'exécution sont uni­ taires, les délais de communication sont égaux à la longueur de la plus courte chaîne reliant les processeurs affectés aux tâches et 'topo' est la topologie du réseau. Nous prouvons que le problème 'UET-UCT-chain' est NP-complet dans le cas où le graphe de pécédence est une arborescence ou une anti-arborescence et que le réseau consiste en une chaîne de longueur illimitée. Ensuite, nous montrons que pour toute topologie fixée avec un nombre arbi­ traire de processeurs, l'ordonnancement d'un graphe arbitraire est un problème NP-complet. Finalement, nous prouvons que l'ordonnancement d'une arborescence sur un réseau en étoile est aussi un problème NP-complet. Numerous complexity results on scheduling problems with communication delays have recently been proved. In these problems, it is assumed that the processor network is entirely connected. In this paper, the processor net­ work is connected but not assumed to be complete, and the commu­ nication delays depend on the distance between the processors. We define 'UET-UCT-topo' as a new classe of scheduling problems : tasks have unit execution time, communication delays are the length of the shortest chain between the processors assigned to the tasks, and 'topo' is a network topology. We prove that 'UET- UCT-chain' is NP-complete even when the task graph is an intree or an outtre and the network is an infinite chain. Afterwards, we show that for any fixed network with an arbitrary number of pro­ cessors, to schedule an arbitrary 'UET-UCT' task graph is NP- complete. Finaly, we prove that to schedule an intree on a star network is NP-complete.