10 janvier 2003

Cyril Briand
LAAS - Toulouse

Titre : "Une procédure par séparation et évaluation progressive pour 
l'ordonnancement robuste de problèmes à une machine"

Résumé : Cet exposé présente une procédure par séparation et évaluation 
progressive (PSEP) pour l'ordonnancement robuste de problèmes à une machine 
1| rj, dj | Lmax. Cette procédure met à profit un théorème de dominance 
démontré dans les années quatre-vingt, préalablement présenté . Par 
considération de la structure d'intervalles définie par les dates de début 
et de fin de chaque travail, ce théorème permet de mettre en évidence un 
ensemble dominant de séquences vis-à-vis du retard algébrique. Cet ensemble 
est caractérisé par considération des sommets et des pyramides associés à 
un problème, deux notions essentielles que nous présentons. L'approche 
d'ordonnancement proposée agit alors sur la structure d'intervalles du 
problème, de façon à restreindre l'ensemble dominant, caractérisé grâce au 
théorème, afin que seules les séquences optimales vis-à-vis du retard 
soient conservées. La séparation d'un noeud de l'arborescence de recherche 
est effectuée par des décalages à droite ou à gauche de certains travaux, 
relativement aux sommets. Nous montrons ensuite comment chaque noeud peut 
être évalué, en temps polynomial, par calcul des bornes inférieure et 
supérieure du retard sur l'ensemble dominant de séquences considéré.