Ce travail présente l'étude de deux types de problèmes d'ordonnancement. Le premier concerne la résolution centralisée et exacte d'un problème à une machine, le second, la résolution distribuée et coopérative d'un problème job shop où chaque machine est assimilée à un acteur possédant sa propre autonomie décisionnelle. Pour ces deux problèmes, des conditions de dominance sont utilisées, dans le premier cas, dans le but de limiter la complexité algorithmique liée à la recherche de solutions admissibles ou optimales, dans le deuxième cas, pour accroître la capacité de chaque acteur à résister aux incertitudes liées aux fluctuations de son environnement. Dans un premier temps, un théorème proposé dans les années quatre-vingt est rappelé, qui, considérant le problème à une machine, permet de caractériser un ensemble de solutions dominantes. Sur la base de ce théorème, nous proposons ensuite de nouvelles conditions analytiques et numériques de dominance permettant de restreindre encore davantage l'ensemble des solutions dominantes. En exploitant ces résultats, des formulations mathématiques originales et efficaces sont présentées, sous forme de programmes linéaires en nombres entiers, pour la modélisation et la résolution du problème à une machine en s'intéressant tour à tour au critère de minimisation du plus grand retard algébrique, puis à celui de minimisation du nombre de travaux en retard. Dans un deuxième temps, nous étudions le problème d'ordonnancement job shop dans un environnement multi-acteur, chaque acteur gérant l'activité d'une machine. Tenant compte de l'autonomie de décision et des objectifs propres de chacun, l'ordonnancement est envisagé sous la forme d'une fonction distribuée où la solution globale résulte d'une coopération entre les différents acteurs, cette solution pouvant évoluer dans le temps au fur-et-à-mesure des prises de décision locales. Ainsi, chaque acteur construisant localement sa propre organisation et n' n'ayant qu'une connaissance part ielle et incertaine de l'organisation des autres, nous proposons que les organisations locales soient construites de façon robuste. Pour cela nous montrons comment, à l'aide des résultats de dominance, maintenir au niveau de chaque acteur un ensemble dominant de solutions ayant une performance au pire bornée. Une nouvelle approche d'ordonnancement est ensuite proposée où les acteurs négocient deux à deux, de façon distribuée, de façon à converger progressivement vers des décisions assurant un compromis satisfaisant entre l'optimisation des objectifs locaux et des objectifs globaux.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00599267 |
| Date | 28 January 2011 |
| Creators | Ourari, Samia |
| Publisher | Université Paul Sabatier - Toulouse III |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0017 seconds