Ce travail s'attache à décrire l'intérêt de l'analyse d'intervalles en ordonnancement. L'analyse d'intervalles considère les relations d'ordres existantes (algèbre de Allen) entres certains intervalles caractéristiques des tâches à ordonnancer. On montre comment, pour certains problèmes particuliers, elle permet de définir des conditions de dominance ou des conditions suffisantes d'optimalité, caractérisant des ensembles remarquables de solutions. Dans le cas de certains problèmes à une machine réputés difficiles, nous montrons comment de telles conditions peuvent être utiles pour déduire des nouvelles formulations de programmation linéaire en nombres entiers très efficaces. De plus, les conditions étant relativement indépendantes des valeurs numériques du problème, on montre aussi leur intérêt pour la caractérisation d'ensembles flexibles et robustes de solutions. D'autres travaux seront également évoqués dans lesquels la notion d'intervalle est centrale.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00558925 |
| Date | 07 December 2009 |
| Creators | Briand, Cyril |
| Publisher | Université Paul Sabatier - Toulouse III |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | habilitation ࠤiriger des recherches |
Page generated in 0.0021 seconds