Program > By author > Guinand Frédéric

En gestion de production comme en informatique parallèle, les tâches à exécuter sont souvent liées par des précédences qui entraînent des délais de communication ou de transport. De la même manière, les machines exécutant ces tâches ne sont pas toujours disponibles, pour des raisons diverses : maintenance, panne, apparition de tâches prioritaires. Ces deux types de problèmes d'ordonnancement ont été étudiés indépendamment, mais aucun travail ne les considère simultanément, même pour le critère de minimisation de la durée totale.

Dans le premier cas, le problème central est l'ordonnancement unitaire (UECT : Unit Execution and Communication Times). Le problème est pseudo polynomial si le graphe de précédence est un arbre. Dans le cas 2 machines, plusieurs algorithmes indépendants existent. Celui proposé par Guinand a une caractéristique intéressante : toutes les communications vont d'une machine vers l'autre (ordonnancement processeur-ordonné). Ceci permet de limiter grandement l'impact de délais de communications différents des valeurs prévues.

Dans le second cas, de nombreuses études considèrent des tâches indépendantes. Des résultats existent pour des graphes de précédence, là encore dans le cas de durées unitaires. En particulier, l'algorithme de Coffman et Graham (algorithme de liste) reste optimal sur deux machines en présence de périodes d'indisponibilités.

Si l'on considère l'ordonnancement d'arbres de tâches unitaires avec communications unitaires et indisponibilités, des difficultés surgissent même pour 2 machines : les algorithmes processeur-ordonnés ne sont plus dominants, et les algorithmes classiques (comme ceux de Coffma et Graham ou de Lawler) non plus. Nous proposons néanmoins un algorithme reprenant les idées de l'algorithme de Guinand , notamment en considérant en bloc l'ordonnancement de sous-arbres. La complexité de cet algorithme et des problèmes avec communications et indisponibilités est discutée. Des résultats expérimentaux complètent cet exposé.