Problème de gestion de projet à contraintes de ressources

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 manufacturé 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é les contraintes de précédence et de ressources.

Soient n tâches et q ressources.

Les ressources sont notées ${\displaystyle R_{k}}$ et leurs capacités sont notées ${\displaystyle B_{k}}$.

Les tâches sont désignées par ${\displaystyle A_{i}}$ et leurs durées sont ${\displaystyle p_{i}}$, une tâche i demande une quantité ${\displaystyle b_{ik}}$ 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: ${\displaystyle A_{0}}$ est le prédécesseur des autres tâches (sommet source du graphe), ${\displaystyle A_{n+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 ${\displaystyle E=\{(i,j)/A_{i}\rightarrow A_{j}\}}$.

Une solution S au problème est un vecteur de ${\displaystyle R_{n+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 ${\displaystyle A_{i}}$ et ${\displaystyle A_{j}}$ telles que ${\displaystyle (A_{i},A_{j})\in E}$ (${\displaystyle A_{i}}$ précède ${\displaystyle A_{j}}$), ${\displaystyle A_{j}}$ ne peut pas commencer avant la fin de ${\displaystyle A_{i}}$, ${\displaystyle S_{j}\geq S_{i}+p_{i}}$
• les contraintes de ressources : à tout instant et pour chaque ressource ${\displaystyle k}$, la somme des demandes des tâches en cours d'exécution n'excède pas ${\displaystyle B_{k}}$

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

• Heuristiques
• Optimisation linéaire
• Programmation par contraintes
• Procédure par séparation-évaluation

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.

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