Soutenance de th
Forum 'Annonces' - Sujet créé le 2005-01-19
Thèse de Doctorat de l'Institut National des Sciences Appliquées de Toulouse
Candidat : LA Hoang Trung
LAAS-CNRS - groupe MOGISA
le 24 janvier 2005 à 10h30 en salle de Conférences du LAAS
Titre : Utilisation d’ordres partiels pour la caractérisation de solutions robustes en ordonnancement
Jury :
Jean-Charles BILLAUT : Professeur à l'Université de Tours (Rapporteur)
Willy HERROELEN : Professeur à l’Université Catholique de Leuven
(Rapporteur)
Marie-Claude PORTMANN : Professeur à l'École des Mines de Nancy
(Examinateur)
Philippe BAPTISTE : Chargé de recherche CNRS (Examinateur)
Cyril BRIAND : Maître de conférence à l’Université Paul Sabatier
(Directeur de thèse)
Jacques ERSCHLER : Professeur à l’INSA Toulouse (Co-directeur de thèse)
François ROUBELLAT : Directeur de recherche CNRS (Invité)
Résumé:
Ce travail s’intéresse à la caractérisation hors ligne d’ensembles de
solutions en ordonnancement destinés à offrir une flexibilité. Il s’inscrit dans le champ de l’ordonnancement robuste pour lequel on
désire construire un ensemble d'ordonnancements relativement insensible, du point de vue de ses performances, aux événements imprévus survenant lors de la mise en œuvre en environnement perturbé. L’approche robuste proposée est de type proactif-réactif. Elle s’appuie sur les notions de structures d’intervalles et de conditions de dominance (ou de conditions suffisantes) vis-à-vis de l’admissibilité ou de l’optimalité de solutions en ordonnancement.
Ce travail s’est particulièrement focalisé sur la phase proactive où il s'agit d’anticiper la mise en œuvre de l’ordonnancement, en construisant au plus tôt une organisation relativement insensible aux perturbations, tout en disposant d’indicateurs relatifs à la performance temporelle. Dans ce cadre, nous montrons en particulier l’intérêt de certains ordres partiels, établis sur la base de corps d’hypothèses restreints, permettant d’une part la détermination d’une performance au mieux et au pire de l’ensemble de solutions caractérisé, et d’autre part, le calcul d’indicateurs de flexibilité.
Dans un premier temps, le problème d’ordonnancement à une machine est étudié. Pour ce problème, un ordre partiel dominant basé sur une analyse de structure d’intervalles est décrit. Cet ordre partiel caractérise un ensemble dominant de solutions de cardinalité calculable, dont la performance au mieux et au pire, en terme de retard algébrique, peut être déterminée en temps de calcul polynomial. Deux approches d’ordonnancement robuste sont ensuite proposées permettant soit de caractériser toutes les séquences optimales contenues dans l’ensemble dominant initial, soit de trouver un compromis flexibilité / performance acceptable.
Dans un deuxième temps, les problèmes d’ordonnancement sur plusieurs machines sont considérés. Un ordre partiel suffisant est d'abord proposé pour le problème flow shop de permutation à deux machines. Deux algorithmes, utilisant les résultats obtenus pour le problème à une machine, sont ensuite présentés dans le cadre de problèmes de type job shop.
Mots-clés :
Ordonnancement robuste, Ordres partiels, Aide à la décision,
Incertitude, Flexibilité, Structure d’intervalles, Dominance.
Candidat : LA Hoang Trung
LAAS-CNRS - groupe MOGISA
le 24 janvier 2005 à 10h30 en salle de Conférences du LAAS
Titre : Utilisation d’ordres partiels pour la caractérisation de solutions robustes en ordonnancement
Jury :
Jean-Charles BILLAUT : Professeur à l'Université de Tours (Rapporteur)
Willy HERROELEN : Professeur à l’Université Catholique de Leuven
(Rapporteur)
Marie-Claude PORTMANN : Professeur à l'École des Mines de Nancy
(Examinateur)
Philippe BAPTISTE : Chargé de recherche CNRS (Examinateur)
Cyril BRIAND : Maître de conférence à l’Université Paul Sabatier
(Directeur de thèse)
Jacques ERSCHLER : Professeur à l’INSA Toulouse (Co-directeur de thèse)
François ROUBELLAT : Directeur de recherche CNRS (Invité)
Résumé:
Ce travail s’intéresse à la caractérisation hors ligne d’ensembles de
solutions en ordonnancement destinés à offrir une flexibilité. Il s’inscrit dans le champ de l’ordonnancement robuste pour lequel on
désire construire un ensemble d'ordonnancements relativement insensible, du point de vue de ses performances, aux événements imprévus survenant lors de la mise en œuvre en environnement perturbé. L’approche robuste proposée est de type proactif-réactif. Elle s’appuie sur les notions de structures d’intervalles et de conditions de dominance (ou de conditions suffisantes) vis-à-vis de l’admissibilité ou de l’optimalité de solutions en ordonnancement.
Ce travail s’est particulièrement focalisé sur la phase proactive où il s'agit d’anticiper la mise en œuvre de l’ordonnancement, en construisant au plus tôt une organisation relativement insensible aux perturbations, tout en disposant d’indicateurs relatifs à la performance temporelle. Dans ce cadre, nous montrons en particulier l’intérêt de certains ordres partiels, établis sur la base de corps d’hypothèses restreints, permettant d’une part la détermination d’une performance au mieux et au pire de l’ensemble de solutions caractérisé, et d’autre part, le calcul d’indicateurs de flexibilité.
Dans un premier temps, le problème d’ordonnancement à une machine est étudié. Pour ce problème, un ordre partiel dominant basé sur une analyse de structure d’intervalles est décrit. Cet ordre partiel caractérise un ensemble dominant de solutions de cardinalité calculable, dont la performance au mieux et au pire, en terme de retard algébrique, peut être déterminée en temps de calcul polynomial. Deux approches d’ordonnancement robuste sont ensuite proposées permettant soit de caractériser toutes les séquences optimales contenues dans l’ensemble dominant initial, soit de trouver un compromis flexibilité / performance acceptable.
Dans un deuxième temps, les problèmes d’ordonnancement sur plusieurs machines sont considérés. Un ordre partiel suffisant est d'abord proposé pour le problème flow shop de permutation à deux machines. Deux algorithmes, utilisant les résultats obtenus pour le problème à une machine, sont ensuite présentés dans le cadre de problèmes de type job shop.
Mots-clés :
Ordonnancement robuste, Ordres partiels, Aide à la décision,
Incertitude, Flexibilité, Structure d’intervalles, Dominance.