Titre : Polyèdres et reconfiguration dynamique d'autocommutateurs répartis.

Présentateur : Renaud Sirdey (Nortel, Heudiasyc)

Résumé :
Cet exposé sera consacré à l'étude d'un problème d'ordonnancement fortement 
NP-difficile à contraintes de ressources, lié à l'opérabilité de certains systèmes 
répartis temps réel à haute disponibilité.

Nous présenterons principalement une méthode de résolution exacte basée sur 
l'étude de deux polytopes : les polytopes des sous-tournois sans circuit et 
des programmes de déplacement. En particulier, nous présenterons plusieurs 
classes d'inégalités qui définissent des facettes de ces polytopes et 
discuterons des problèmes de séparation associés.

En guise de conclusion, nous illustrerons  la pertinence pratique de  cette approche 
à l'aide de résultats empiriques et discuterons de la généralisation de ces travaux 
à des problèmes de reroutage dans certains réseaux de télécommunications.

Ces travaux sont réalisés dans  le cadre d'une thèse de doctorat dirigée par 
J. Carlier et D. Nace (Heudiasyc) et en collaboration avec H. Kerivin (Limos).