Utilisation d’ordres partiels pour la caractérisation de solutions robustes en ordonnancement

Ce travail s'interesse a la caracterisation hors ligne d'ensembles de solutions en ordonnancement destines a offrir une certaine flexibilite. Il s'inscrit dans le champ de l'ordonnancement robuste pour lequel on desire construire un ensemble d'ordonnancements relativement insensible, du point de vue de ses performances, aux evenements imprevus survenant lors de la mise en Suvre en environnement perturbe. L'approche robuste proposee est de type proactif-reactif. Elle s'appuie sur les notions de structures d'intervalles et de conditions de dominance (ou de conditions suffisantes) vis-a-vis de l'admissibilite ou de l'optimalite de solutions en ordonnancement. Ce travail s'est particulierement focalise sur la phase proactive ou il s'agit d'anticiper la mise en Suvre de l'ordonnancement, en construisant au plus tot une organisation relativement insensible aux perturbations, tout en disposant d'indicateurs relatifs a la performance temporelle. Dans ce cadre, nous montrons en particulier l'interet de certains ordres partiels, etablis sur la base de corps d'hypotheses restreints, permettant d'une part la determination d'une performance au mieux et au pire de l'ensemble de solutions caracterise, et d'autre part, le calcul d'indicateurs de flexibilite. Dans un premier temps, le probleme d'ordonnancement a une machine est etudie. Pour ce probleme, un ordre partiel dominant base sur une analyse de structure d'intervalles est decrit. Cet ordre partiel caracterise un ensemble dominant de solutions de cardinalite calculable, dont la performance au mieux et au pire, en terme de retard algebrique, peut etre determinee en temps de calcul polynomial. Deux approches d'ordonnancement robuste sont ensuite proposees permettant soit de caracteriser toutes les sequences optimales contenues dans l'ensemble dominant initial, soit de trouver un compromis flexibilite / performance acceptable. Dans un deuxieme temps, les problemes d'ordonnancement sur plusieurs machines sont consideres. Un ordre partiel suffisant est d'abord propose pour le probleme flow shop de permutation a deux machines. Deux algorithmes, utilisant les resultats obtenus pour le probleme a une machine, sont ensuite presentes dans le cadre de problemes de type job shop.