Problème de gestion de projet à contraintes de ressources

Problème de gestion de projet à contraintes de ressources

Le problème de gestion de projet à contraintes de ressources est un problème d'optimisation combinatoire, étudié en ordonnancement. Il est connu sous l'acronyme anglophone RCPSP ( Resource-Constrained Project Scheduling Problem ).

Le problème est NP-difficile au sens fort, il ne peut donc être résolu optimalement que par des algorithmes de complexité exponentielle. L'état de l'art permet de le résoudre optimalement dans un temps raisonnable, sur des instances de 60 tâches au plus.

Sommaire

Description

Concepts

Les ressources sont des moyens de production renouvelables, mais limités en capacité. Une équipe de quatre ouvriers ayant les mêmes compétences peut être considérée comme une ressource de capacité 4.

Les tâches sont des travaux définis par une durée et une quantité de chaque ressource qui est nécessaire à son exécution. Les tâches sont supposées non-préemptives: une fois que l'exécution a commencé, elles se poursuit sans interruption jusqu'à la fin. Un bien manufacturier peut prendre deux heures de fabrication, et nécessiter le travail de deux ouvriers et d'une machine.

Il existe entre les tâches des relations de précédence, qui signifient classiquement qu'une tâche ne peut débuter que si certaines autres tâches sont finies. Ces relations permettent de représenter l'organisation du projet par un graphe de précédence ( ou réseau PERT) : une tâche est figurée par un nœud, chaque relation de précédence est un arc orienté du prédécesseur vers le successeur, qui est valué par la durée du prédécesseur. Un graphe de précédence ne doit pas présenter de circuit, une tâche ne pourrait, directement ou indirectement, être son propre prédécesseur.

Classiquement, le problème consiste à minimiser la date de fin du projet, étant données les contraintes de précédence et de ressources.

Formalisation

Soient n tâches et q ressources.

Les ressources sont notés Rk et leurs capacités sont notées Bk.

Les tâches sont désignées par Ai et leur durées sont pi, une tâche i demande une quantité bik de la ressource k. Deux tâches fictives sont ajoutées en général, elles ont une durée nulle et ne consomment pas de ressources: A0 est le prédécesseur des autres tâches ( sommet source du graphe ), An + 1 est le successeur de toutes les tâches ( sommet puits du graphe de précédence ). Les précédences sont déclarées par un ensemble E = \{(i,j) / A_i  \rightarrow A_j\}.

Une solution S au problème est un vecteur de Rn + 2 contenant les dates de début de chacune des tâches.

Il existe deux types de contraintes:

  • les contraintes de précédence: soient des tâches Ai et Aj telles que (A_i,A_j)\in E (Ai précède Aj), Aj ne peut pas commencer avant la fin de Ai, S_j \geq S_i + p_i
  • les contraintes de ressources: à tout instant et pour chaque ressource k, la somme des demandes des tâches en cours d'exécution n'excède pas Bk

Méthodes de résolution

Un certain nombre d'outils ont été employés pour résoudre le problème:

Algorithmes de liste

Les premières méthodes, créées dans les années 1960, sont des heuristiques à base de listes. Les listes de priorité définissent une priorisation dans l'exécution des tâches, selon des critères souvent heuristiques comme le temps de traitement de tâches ou la marge. Une liste de priorité doit respecter les contraintes de précédence.

L'algorithme d'ordre strict consiste à placer les tâches une par une, au plus tôt possible, dans l'ordre exact de la liste de priorités.

t\leftarrow 0
Tant que la liste de priorité est non vide
  soit la tâche i que l'on retire au début de la liste de priorité
  r_i = max(t,max_{j\in Pred(i)}(t_j+p_j)) la date à la quelle on peut ordonnancer i au plus tôt (pj est la durée de la tâche j)
  soit t_i \geq r_i, la première date à la quelle les ressources sont disponibles pour l'exécution
  placer la tâche à la date ti
  t\leftarrow t_i
Fin Tant Que

Détermination d'une borne inférieure

Etant donnée la complexité du problème, il est souvent illusoire de vouloir déterminer des solutions exacte au problème. En recherche opérationnelle, pour évaluer concrètement une méthode de résolution, on évalue la qualité d'une solution en comparant la date de fin obtenue Cmax avec une borne inférieure LB. La borne inférieure est une valeur qu'on sait inférieure à la date de fin de la solution optimale, mais on doit obtenir une valeur assez haute pour bien approcher la valeur optimale. La qualité d'une solution se mesure en pourcentage d'écart avec la borne inférieure: \frac{C_{max}-LB}{LB}.

Méthode du chemin critique

Chemin critique amélioré

Raisonnement énergétique

Extensions

Le modèle basique du RCPSP a été adapté à de nombreuses applications industrielles, d'où l'apparition de variantes du problème.

Gestion de projet multi-compétence

Cette variante est adaptée à la planification de projet dans des sociétés de service, notamment des SSII. On définit un ensemble de compétences, les ressources représentent les personnes participant au projet, la capacité de chaque ressource est 1. Une tâche ne se définit plus par des quantités exigées de chaque ressource, mais par des nombre de personnes ayant telles compétences. Par exemple, une tâche "Tests unitaires" peut nécessiter deux personnes ayant la compétence "Développeur" et une personne ayant la compétence "Analyste".

Tâches multi-mode

Une même tâche peut être exécutée de différentes manières, ou modes. Chaque mode définit une durée propre et des demandes en ressources. Le choix d'un mode pour exécuter un tâche fait partie du problème.

Ordonnancement robuste

Des approches d'ordonnancement robuste ont été développées pour le RCPSP. Les modèles robustes en gestion de projet considèrent quatre types de perturbations[1]:

  • perturbations du graphe de projet: des tâches ( ou des liens de précédence ) sont ajoutées ou supprimées
  • perturbations sur les tâches: modifications des durées, des demandes
  • perturbations sur les ressources: des ressources deviennent indisponibles (pannes, absences) ou leur capacité est temportairement limitée
  • changements de délais

Voir aussi

Articles connexes

Sources et références

  1. Gang Yu,Xiangtong Qi Disruption management : framework, models and applications, 2004

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de gestion de projet à contraintes de ressources de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Projet — Un projet est un engagement irréversible dont le résultat est incertain, il vise à répondre à un besoin exprimé ou à résoudre une problématique explicitée et nécessite le concours et l’intégration d’une grande diversité de contributions Le… …   Wikipédia en Français

  • Problème d'ordonnancement — Théorie de l ordonnancement Pour les articles homonymes, voir Ordonnancement. La théorie de l ordonnancement est une branche de la recherche opérationnelle qui s intéresse au calcul de dates d exécution optimales de tâches. Pour cela, il est très …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Projet de la Baie James — La centrale LG 1. Le Projet de la Baie James (ou Complexe La Grande) désigne une série d aménagements hydroélectriques construits pour Hydro Québec sur la Grande Rivière, dans le Nord du Québec, entre 1974 et 1996. Le bassin versant du Complexe… …   Wikipédia en Français

  • Projet de la baie-james — La centrale LG 1. Le Projet de la Baie James (ou Complexe La Grande) désigne une série d aménagements hydroélectriques construits pour Hydro Québec sur la Grande Rivière, dans le Nord du Québec, entre 1974 et 1996. Le bassin versant du Complexe… …   Wikipédia en Français

  • Problème du sac à dos — Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un… …   Wikipédia en Français

  • Gestion prévisionnelle des emplois et des compétences — La Gestion prévisionnelle de l’emploi et des compétences (GPEC) est une gestion anticipative et préventive des ressources humaines, fonction des contraintes de l’environnement et des choix stratégiques de l’entreprise. C est aussi une… …   Wikipédia en Français

  • Théorie de l'ordonnancement — Pour les articles homonymes, voir Ordonnancement. La théorie de l ordonnancement est une branche de la recherche opérationnelle qui s intéresse au calcul de dates d exécution optimales de tâches. Pour cela, il est très souvent nécessaire d… …   Wikipédia en Français

  • Théorie des contraintes — La Théorie des Contraintes (Theory of Constraints ou TOC en Anglais) est un référentiel de connaissances, de méthodes et d’outils de management interdisciplinaires des organisations. L’auteur principal est Eliyahu M. Goldratt, avec d’autres… …   Wikipédia en Français

  • Theorie des contraintes — Théorie des contraintes La Théorie des Contraintes (TOC) est un référentiel de connaissances, de méthodes et d’outils de management interdisciplinaires des organisations. L’auteur principal est Eliyahu M. Goldratt, avec d’autres contributeurs.… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”