L'ordonnancement multicritère : un florilège de combinatoire, logique et algorithmique

La théorie de l'ordonnancement a fait l'objet de nombreuses études depuis les années 50. Ordonnancer, c'est prévoir dans le temps l'exécution d'un ensemble de tâches, ou travaux, sur un ensemble de ressources, ou machines, avec comme objectif l'optimisation d'un (ou de plusieurs) critère(s). Depuis les travaux pionniers de Johnson en 1954, la majorité des travaux publiés dans la littérature concerne des problèmes monocritères. Fort heureusement, s'appuyant sur des résultats de l'optimisation multicritère, cette tendance à commencé à s'inverser depuis une vingtaine d'année. L'ordonnancement multicritère commence à trouver sa place comme un champ d'étude intéressant, avec ses particularités, au sein de la théorie de l'ordonnancement. L'objectif de ce séminaire est de présenter les problématiques de base qui se posent en ordonnancement. Cette partie, de nature introductive, doit permettre à l'auditeur néophyte de comprendre les enjeux : ce qu'est un problème d'ordonnancement, comment il peut être résolu et surtout l'aspect combinatoire qu'il met en jeu. Ensuite, le séminaire sera dédié à la résolution d'un problème d'ordonnancement bicritère basique, résolution largement illustrée qui permettra de comprendre les liens existants entre les problèmes d'ordonnancement monocritère et multicritère.