Auteurs: Vincent T'kindt, Carl Esswein. Laboratoire d'Informatique, Ecole d'Ingénieurs en Informatique pour l'Industrie, 64 avenue Jean Portalis, 37200 Tours Titre: Une procédure par séparation et évaluation dédiée à l'énumération des optima de Pareto pour les problèmes d'ordonnancement multicritères : application à un problème à une machine. Résumé: Nous considérons le problème d'ordonnancement où n travaux doivent être ordonnancés sur une unique machine. Chaque travail est défini par un temps opératoire, un poids, et une date de fin souhaitée. L'objectif est de minimiser le plus grand retard algébrique ainsi que la date de fin moyenne pondérée. Nous nous intéressons dans ce travail à l'énumération des solutions de meilleur compromis, i.e. à l'énumération des optima de Pareto stricts. Ce problème bicritère est NP-difficile au sens fort. Une approche classique en ordonnancement multicritère, lorsque l'on souhaite énumérer les optima de Pareto stricts, est l'approche e-contrainte qui consiste à minimiser un critère sachant que les autres font l'objet d'une contrainte de borne. On se ramène ainsi à un nouveau problème monocritère. L'énumération consiste alors à résoudre une succession de problèmes e-contraints. Chacun de ces problèmes, s'il est résolu optimalement, permet d'obtenir un optimum de Pareto. Cela peut être fait, par exemple, par une procédure par séparation et évaluation. Dans ce cas, un arbre de recherche sera reconstruit depuis la racine pour chaque nouveau problème e-contraint, ce qui au final peut conduire à l'exploration multiple de branches stériles. Par ailleurs aucune information sur la structure de l'ensemble des optima de Pareto ne peut être utilisée. Pour le problème d'ordonnancement introduit précédemment, nous présentons deux algorithmes optimaux. Le premier utilise une procédure par séparation et évaluation classique pour résoudre chaque problème e-contraint. Le second est une adaptation d'une procédure par séparation et évaluation et qui intègre des propriétés du problème bicritère. Chaque noeud n'est construit qu'une fois pour tout le problème d'énumération. Les branches stériles des différents arbres de recherche parcourus par le premier algorithme ne sont parcourues qu'une unique fois. Des résultats expérimentaux viennent illustrer le comportement de ces deux algorithmes.