Les différents graphes permettant de modéliser les problèmes d'ordonnancement de projet
Hypothèse particulière
Dans cette partie, nous allons supposer que nous disposons de toutes les ressources nécessaires en quantité suffisante pour qu'il n'y ait pas de contraintes liées à l'utilisation des ressources. On dit alors que les ressources sont illimitées.
Le problème d'ordonnancement est alors un problème exclusivement temporel, dans lequel il faut décider quand les tâches doivent être réalisées.
Pour placer les tâches dans le temps, nous avons besoin de connaître leur durée et si des contraintes technologiques sur la réalisation des tâches font qu'une tâche A doit être totalement (ou partiellement) terminée avant que l'on puisse commencer la tâche B, c'est ce que l'on appelle une contrainte de précédence.
C'est le cas le plus simple de la famille dite d'ordonnancement de projet.
Définition : Modélisation par des équations
N est l'ensemble des tâches à ordonnancer.
P est l'ensemble des couples de tâches où la tâche i doit précéder la tâche j.
ti est l'instant de début de la tâche i (1 ≤ i ≤ n).
di est la durée de la tâche i.
ai,j est le minimum de temps qui doit s'écouler entre le début de la tâche i et le début de la tâche j, lorsque la tâche i doit précéder la tâche j.
Les contraintes du problème sont des contraintes de précédence :
∀ (i,j) ∈ P : ti + ai,j ≤ tj
En général, lorsqu'une tâche i doit précéder une tâche j, on attend que la tâche i soit complétement terminée avant de démarrer la tâche j. Dans ce cas, ai,j est égal à di.
Néanmoins, il y a des cas où un temps de refroidissement ou de séchage doit être intercalé entre les deux tâches et dans ce cas, ai,j est plus grand que di.
Il y a d'autres cas où, par exemple, la tâche i est une succession de petites tâches en série (que l'on ne veut pas décrire en détail) et dans ce cas, il est possible que la tâche j puisse démarrer avant la fin de la tâche i et ai,j est plus petit que di.
Modélisation des solutions du problème par un diagramme de Gantt
Pour représenter la solution d'un problème d'ordonnancement, la solution la plus ancienne, la plus intuitive et la plus connue consiste à utiliser un diagramme de Gantt.
Il consiste tout simplement à représenter les tâches par des barres horizontales dont la longueur est proportionnelle à la durée de la tâche et de les positionner sur l'axe des temps (ici l'axe horizontal). Sur la verticale, on espace simplement les barres représentant les tâches pour qu'elles ne se chevauchent pas.
Lorsqu'il s'agit d'un gros problème, on regroupe de manière logique les tâches par famille ou on utilise des couleurs différentes, c'est ce que nous avons fait sur le diagramme de Gantt proposé ci-dessous.
On voit bien, par exemple ici, que l'on ne peut commencer 2, 3 et 4 que quand la tâche 1 est terminée.
De même, on ne peut commencer 8, 9 et 10 que quand la tâche 4 est terminée etc.
Modélisation du problème d'ordonnancement de projet par des graphes
Historiquement, le premier graphe qui a été proposé, aux États Unis, est le graphe "PERT" ou graphe potentiel-événements.
Presque à la même période, le graphe potentiel-tâches a été proposé, en France, par Bernard Roy.
Pour des raisons historiques, nous présentons d'abord le graphe potentiel-événements en montrant immédiatement sur des petits exemples les problèmes que son utilisation induit.
Le graphe potentiel-tâches, même s'il est plus éloigné du diagramme de Gantt, ne présente pas ces problèmes.
Aussi, la meilleure pratique que nous recommandons consiste à utiliser
la liste des prédécesseurs pour entrer les contraintes de précédence et les durées correspondantes dans les programmes,
le graphe potentiel-tâches pour modéliser le problème, le représenter graphiquement et décrire les algorithmes,
le diagramme de Gantt pour transmettre la solution obtenue aux personnes qui auront à réaliser les tâches.
Le graphe potentiel-événements ou graphe "PERT"
Il correspond à une déformation du diagramme de Gantt.
Un arc représente généralement une tâche (ou une partie de tâche) qui se déroule.
L'origine de l'arc représente l'événement "la tâche peut commencer" (ou un morceau de tâche peut commencer).
La fin de l'arc représente l'événement "la tâche est finie" (ou un morceau de tâche est fini).
Si les tâches B et C suivent la tâche A alors on rassemble les événements "la tâche A est finie", "la tâche B peut commencer" et "la tâche C peut commencer" en un point événements multiples, où arrive l'arc représentant la tâche A et commencent les arcs représentant les tâches B et C.
Premier exemple où le graphe potentiel-événements pose un problème
La tâche C doit suivre les tâches A et B, alors que la tâche D ne doit suivre que la tâche A.
Les événements multiples que l'on doit réunir en un point événement ne sont pas les mêmes.
Cela oblige à créer deux points événements et une tâche fictive de durée 0 entre ces deux points événements comme le montre le graphique suivant (où les événements sont numérotés arbitrairement de 0 à 4).
Deuxième exemple où le graphe potentiel-événements pose un problème
La tâche B peut suivre immédiatement la tâche A, alors que la tâche C nécessite que l'on attende au minimum 4 unités de temps après la fin de la tâche A.
Cela oblige à ajouter une tâche fictive de durée 4 entre la fin de la tâche A et le début de la tâche C, comme le montre le graphique suivant (où les événements sont numérotés arbitrairement de 0 à 4).
Remarque : Non unicité du graphe potentiel-événement
Il y a en général plusieurs manières pour ajouter des tâches fictives de manière à prendre en compte les cas où on est obligé d'ajouter des arcs correspondant à des tâches fictives. En conséquence, il n'y a pas unicité du graphe potentiel-événement correspondant à un problème d'ordonnancement de projet : pas le même sous-ensemble de points et/ou le même sous-ensemble d'arcs. Toute une communauté scientifique s'est intéressé au problème de trouver le meilleur graphe PERT correspondant à un problème. Il est en fait beaucoup plus simple d'utiliser le graphe potentiel-tâches que nous allons présenter maintenant.
Définition : Graphe potentiel-tâches
Un point est associé à chaque tâche.
Un arc entre deux points correspond à une contrainte de précédence entre deux tâches.
La valeur attribuée à l'arc représente le temps minimum qui doit s'écouler entre le début de la tâche origine de l'arc et le début de la tâche extrémité de l'arc.
Non nécessité de tâches fictives dans le graphe potentiel tâche
Les deux graphes potentiel-tâches ci-dessus correspondent aux deux exemples de graphes potentiel-événements où on avait été obligé d'ajouter des tâches fictives, on voit de manière évidente que ces graphes sont plus simples que les graphes précédents.
Remarque : "Quasi-unicité" du graphe potentiel-tâches
Le graphe potentiel-tâches est normalement unique, sauf si on y inclut des contraintes de précédence inutiles :
par exemple, si on a A qui précède B et B qui précède C, il est inutile de dire que A précéde C sauf si la valeur sur l'arc qui va de A à C est strictement supérieure à la valeur de l'arc qui va de A à B augmentée de la valeur de l'arc qui va de B à C.
Remarque : Possibilité d'utiliser des valeurs négatives sur les arcs
Dans un graphe potentiel-tâches, la valeur ai,j peut être négative.
Comme on a : ti + ai,j ≤ tj . Cela donne : ti ≤ tj - ai,j
Ce qui signifie que la tâche i peut commencer au plus tard valeur absolue ( ai,j) unité de temps après le début de j.
Exemple : Utilisation de deux arcs de signes inverses entre deux tâches
Les contraintes de précédence du petit graphe ci-dessus signifient que B peut commencer au plus tôt 10 unités de temps après le début de A et au plus tard 50 unités de temps après le début de A.
Le début de la tâche B doit donc être placé dans un intervalle entre 10 et 50 unités de temps après le début de la tâche A.
Fondamental :
Un graphe potentiel-tâches peut comporter des circuits (lorsqu'il y a des valeurs négatives sur certains arcs), mais ne peut en aucun cas contenir des circuits de longueur strictement positive.
En présence de circuits de longueur strictement positive, le problème d'ordonnancement n'a pas de solution, puisque l'instant de début d'une tâche du circuit devrait être strictement supérieur à lui-même.
