Soutenance mémoire
La méthode réactive
La méthode réactive n’ essaye pas de combattre l’ incertitude en créant un plan d’ordonnancement capable d’anticiper d’éventuelles incel1itudes, mais revoit et ré opti mise l’ ordonnancement lors qu’un événement se produit. Les principaux auteurs sur le sujet sont Sabuncuoglu et Bayiz (2000), Szelke et Kerr (1 994) et Vieira et al. (2003). L’ ordonnancement réactif nécessite des règles d’actions pow’ « réparer » le plan d’ordonnancement. Un exemple type de ces méthodes est la « ri ght shift rule » (règle de mise au plus tard) (Sadeh et al. , 1993; Smith, 1994). Cette règle repousse à plus tard les tâches affectées par l’évènement imprévu. Cette méthode ne peut mener qu’a des résultats médiocres, car ell e ne revoit pas l’ ordonnancement complet des activités. Une autre approche consiste en un ré ordonnancement compl et des acti vités. Cette technique fa it appel à une heuristique spéciale afin que le nouveau plan d’ordonnancement diffère le moins possible du pl an ori ginal. Il faut donc introduire une stratégie de perturbation minimale. Une tell e technique requiert l’utilisation d’algorithmes exacts ou sub-optimaux utilisant des fonctions minimisant la somme des différences des dates de début des acti vités entre le pl an initial et le nouveau pl an. (El Sakkout and Wallace, 2000). Alagoz and Azizoglu(2003), Calhoun et al. (2002) proposent un ré ordonnancement des activités en ayant pour but de minimiser le nombre d’acti vités changées entre le progranID1e initial et le programme final.
La méthode PERT
PERT est une abréviation anglaise de « Program Eva luation and Review Technique», ce qui signifi e progranun e d’évaluation et d’examen de projet. Dans la méthode PERT les durées des tâches sont le plus souvent représentées par des distributions Bêta.
Une distribution Bêta est définie sur un intervalle fini, donc elle possède une bome inférieure et une bome supérieure. Son mode, c’est-à-dire la valeur max imale de sa distribution peut se situer n’ importe où dans cet interva lle. Ainsi on défini la distribution de la durée des tâches grâce à trois estimations:
– La durée minimale (a)
– La durée la plus probable (m)
– La durée maximale (b)
La méthode stochastique
L’ordonnancement stochastique permet de planifier les tâches d’un projet avec des durées incertaines, afin de minimiser la durée du projet attendu sans contrainte de ressources renouve labl es et avec des relations de précédence. La méthode consiste en une générati on aléatoire de tous les scénarios possibles en fonction des distributions de probabilités des durées des tâches. Afi n de faire le tri dans l’ensemble des scénari os générés, il fa ut mettre en pl ace des stratégies d’ordonnancement. L’obj ectif général consiste à créer une poli tique d’ordonnancement qui minimise la durée attendue du proj et. Fernandez (1 995), Fernandez et al. (1996, 1998) et Pet-Edwards et al. ( 1998) ont modélisé le problème d’optimisation correspondant sous la forme d’une programmati on stochastique multi étape .
Radermacher (1985) a défini les «early start poli cies » (politique du début au plus tôt). Ce concept minimise les solutions interdites, c’est à dire l’exécution de deux tâches sans relation de précédence simultanément alors qu’ell es utilisent les mêmes ressources. Igelmund and Radermacher (l 983a,b), ont introduit les politiques pré-sé lectives (PRS). Le princ ipe est que pom chaque solution interdite il faut fa ire en sorte que l’une des activités commence quand l’autre est terminée. Mohring et Stork (2000) ont introduit une représentation de présélection appelée «waiting conditions» (conditions d ‘attente). Ces conditions peuvent être modélisées par des conditions de précédences fo rmulées avec des fonctions booléennes OU et ET. Il faut savoir que les politiques pré-sélectives sont limitées par la capacité de ca lcul des ordinateurs. Ai nsi Mohri ng and Stork (2000) ont défini les politiques de pré-sé lecti ons linéaires (LIN). Cette méthode vise à pl anifier dans un premi er temps les ensembl es d’ordonnancement qui respectent les conditions de précédence ori ginell es. Au lieu d’utiliser des politiques d’ordonnancement pour trier les différents scénarios générés aléatoirement, on peut fa ire appel à des méthodes heuristiques. (Pet-Edwards, 1996; Golenko-Ginzburg and Gonik, 1997; Tsa i and Genm1il, 1998). Ces techniques sont encore émergentes.
La méthode robuste
La méthode robuste consiste en la création d’un ordonnancement robuste c’est-à-dire qu’il est sensé supporter les imprévus, c’est ce qu’on appelle la tolérance aux fautes. Cette tolérance est générée par des redondances, au niveau des ressources, avec des ressources en stand-by (Ghosh, 1996), au niveau du temps en incluant des tâches « réserves » qui donnent du temps en cas de problème. (Ghosh et Al. , 1995). La pure redondance des ressources est plutôt irréaliste dans un environnement projet, car ce ll es-ci feraient doubler les coûts. Une redondance sur le temps semble plus adéquate, mais dans un environnement multi-projet on est loin d’une étude sur un seul projet.
Gao (1 995) a développé la méthode de protection temporell e, basée sur la probabilité non null e de panne des ressources. La durée des acti vités est égale à la durée originelle des activités augmentée de la durée probable des pannes sensées se produire durant son exécution. Cette technique est basée sur les statistiques propres aux ressources (mean time fa ilure, mean time to repair) (temps moyen d’apparition des défauts, temps moyen de réparation), ce qui rend cette approche difficil ement applicable si la plus part des ressources des tâches sont humaines.
Davenport et al. (2001 ) proposent une méthode d’améliorati on de la protection temporelle, grâce à ses techniques: « time windows slack » (fenêtre de temps creux) et « foc used time windows slack » (fenêtre de temps creux limitée). Cette technique n’inclut pas le tampon de temps dans la durée de la tâche. Ainsi le tampon de temps n’est pas utilisé pour une tâche mais pour plusieurs, le tampon de temps est placé aux endroits où il y a le plus de risque.
L’analyse de la sensibilité
De nombreuses recherches récentes portent sur l’analyse de sensibilité des ordonnancements de machines (Hall et Posner, 2000 a,b). L’analyse de sensibilité cherche à répondre aux questions du type « qu’est ce qui se passe si .. . ? » ou encore :
➢ Quelle est la limite si je modifie un paramètre pour que la solution reste optimale?
➢ Pour un changement de paramètre donné, quel est le nouveau coût optimal?
➢ Pour un changement de paramètres donnés, quelle est la nouve lle solution optima le?
➢ Quand est-ce qu’un ordonnancement est optimal?
➢ Quand est-ce que la va leur de la fonction obj ective devient optimale?
➢ Quel type d’analyse de sensibilité est adéquat pour évaluer la robustesse d ‘ un ordonnancement?
➢ Quel type d’analyse de sensibilité peut être utilisé sans utiliser l’ensemble des déta ils de la solution?
➢ Etc .. .
Ce type d’ordonnancement vise à établir un ordonnancement qui ne cra int pas ou très peu les sources d’incertitude.
|
Table des matières
INTRODUCTION
CHAPITRE 1
LES DIFFÉRENTES APPROCHES D ‘ORDONNANCEMENT SOUS INCERTITUDE
1. 1 La méthode réactive
1.2 La méthode PERT
1.3 La méthode stochastique
l A L’ ordonnancement fl ou
1.5 La méthode robuste
1. 6 L’anal yse de la sensibilité
1 .7 La méthode de la chaîne critique
1.8 La méthode GERT
1.9 Conclusion
CHAPITRE II
MÉTHODE DES INTERVA LLES
2. 1 La méthode des intervalles
2. 1.1 revue de 1 ittérature appliquée à la méthode
2.2 Traitement du probl ème
2.2. 1 L’étude des scénarios
2.2.2 Méthode Monte Carlo
2.2 .3 Algorithme de fourmi
2.2.4 Conclusion
CHAPITRE III
COMPARAISON DES MÉTHODES
3. 1 Résultats
3.1.1 le temps d’exécution
3.1.2 Précision
CONCLUSION
Télécharger le rapport complet
