Loading...
Please wait, while we are loading the content...
Similar Documents
Nouvelles approches pour la résolution du problème d'ordonnancement de projet à moyens limités
| Content Provider | Semantic Scholar |
|---|---|
| Author | Koné, Oumar |
| Copyright Year | 2009 |
| Abstract | Dans ce travail de these, nous avons etudie deux types de problemes d'ordonnancement. La majeure partie concerne le probleme d'ordonnancement de projet a moyens limites (RCPSP). Le probleme d'ordonnancement des operations de manutention dans un entrepot de transbordement ("crossdocking") est egalement traite avec une moindre importance. Dans une premiere partie (la plus etendue), nous abordons le RCPSP. A partir de modelisations utilisant la programmation lineaire en nombres entiers, nous avons propose deux nouvelles formulations de ce probleme, utilisant des variables indicees par des evenements. Dans l'une d'entre elles, on utilise une variable binaire pour marquer le debut de l'execution de chaque activite et une autre variable pour marquer sa fin. Dans la seconde proposition, une seule variable est utilisee. Elle identifie les evenements apres lesquels l'activite reste en cours ou debute son execution. De facon generale, comparees a d'autres modeles de la litterature sur divers types d'instances, nos propositions affichent des resultats plus interessants sur les instances contenant des activites aux durees disparates et associees a de longs horizons d'ordonnancement. En particulier, sur ces memes types d'instances mais hautement cumulatives (caracteristiques de base du RCPSP), elles sont egalement les plus performantes. Nous avons egalement aborde la resolution d'une extension du RCPSP consistant a prendre en compte des ressources particulieres, qui peuvent etre consommees en debut d'execution de chaque activite, mais aussi produites a leur fin : il s'agit du RCPSP avec consommation et production de ressources. Afin d'effectuer une comparaison experimentale entre differents modeles, nous avons propose une adaptation de nos formulations basees evenements, des formulations a temps discret de Pritsker et de Christofides, et de la formulation a temps continu basee sur les flots (propose par Artigues sur la base des travaux de Balas). Globalement, les resultats mon trent que nos formulations basees evenements obtiennent les meilleurs resultats sur bon nombre de types d'instances. Dans la seconde partie (plus reduite), nous avons egalement propose un branch-and-bound utilisant des coupes basees sur la frontiere de Pareto, pour la resolution du probleme d'ordonnancement des operations de manutention au sein d'un entrepot de transbordement ("crossdocking"). Les excellents resultats obtenus ont renforce nos interrogations sur la complexite non-prouvee de ce probleme, et ont permis d'etablir par la suite que le probleme est de complexite polynomiale. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://tel.archives-ouvertes.fr/tel-00446704/document |
| Alternate Webpage(s) | https://tel.archives-ouvertes.fr/file/index/docid/446704/filename/These.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
