Une méthode pour caractériser l'ensemble des séquences optimales pour quelques problèmes d'ordonnancement

International audienceDe nombreux problèmes d'ordonnancement ont la particularité d'avoir de nombreuses solutions optimales. C'est le cas par exemple du problème à une machine 1||Lmax (plus grand retard algébrique) ou du problème de flowshop à deux machines F2||Cmax. Pour ces problèmes, on ne s'intéresse en général qu'à une seule solution optimale, alors qu'il peut être intéressant d'en connaître plusieurs. Cela est par exemple motivé par des soucis de flexibilité lors de la mise en oeuvre de l'ordonnancement, ou bien afin de prendre en compte un autre critère d'optimisation. La connaissance de plusieurs solutions optimales peut donc être intéressante. Toutefois, l'énumération implicite des solutions optimales n'est en général pas envisageable, compte tenu du très grand nombre (pouvant être exponentiel) de solutions optimales potentielles. On s'intéresse dans cette communication à la caractérisation de l'ensemble des solutions optimales. Autrement dit, pour certains problèmes d'ordonnancement particuliers, nous allons chercher à établir les caractéristiques des solutions optimales. L'objectif ici n'est pas de caractériser un sous-ensemble des solutions optimales, mais l'ensemble complet de toutes les solutions optimales