Ce travail s'intéresse à la caractérisation hors ligne d'ensembles de solutions en ordonnancement destinés à offrir une certaine 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 Suvre 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 Suvre 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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00009741 |
| Date | 24 January 2005 |
| Creators | La, Hoang Trung |
| Publisher | INSA de Toulouse |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds