Introduction
Dans ce cours nous allons présenter le problème de l’ordonnancement de taches et sa modélisation par les graphes.
Considérons l'exemple suivant :
La construction d'un bâtiment peut être décomposée de manière très schématique dans les activités ou tâches suivantes :
Fondation et maçonnerie
Plan des aménagements intérieurs
Toiture
Installations électriques et sanitaires
Façade
Peintures intérieures
L'exemple est volontairement très simplifié.
Il s'agit de planifier ces différentes activités et plus précisément de déterminer pour chaque tâche la date de début de son exécution. Pour cela, on dispose pour chaque tâche des informations suivantes :
- sa durée
- les tâches qui doivent être terminées afin qu'elle puisse commencer
Les données du problème peuvent être résumées dans le tableau suivant :
Le problème est de déterminer un calendrier d'exécution de ces tâches de manière à terminer les travaux dans les meilleurs délais.
Définition du problème de l'ordonnancement
Un projet est découpé en un ensemble T de tâches pour lesquelles on dispose des informations suivantes:
- chaque tâche i ϵT a une durée di supposée connue avec certitude,
- ces tâches sont liées entre elles par des contraintes de succession,
- les tâches peuvent être affectées de contraintes de localisation temporelle : par exemple, date de début imposée pour une tâche.
Il s'agit de déterminer le calendrier d'exécution de ces tâches, compatible avec les contraintes, de manière à ce que toutes les tâches soient réalisées en un minimum de temps.
Définitions
Un ordonnancement est une solution réalisable du problème.
C'est donc un calendrier possible.
Un ordonnancement optimal est une solution ...optimale !
C'est un calendrier d'exécution qui conduit à la durée totale la plus courte.
Modélisation du problème
On dispose d'un ensemble T de tâches.
Pour chacune d'elles, on a sa durée di.
Les différentes contraintes de succession ou de localisation temporelle ont été recensées.
Comme pour tout problème d'optimisation, on peut mettre en évidence les trois phases :
- que doit-on faire, quelles sont les décisions à prendre ?
- que peut-on faire, quelles sont les contraintes qui limitent ces décisions ?
- quel critère choisit-on entre plusieurs décisions ?
Les décisions à prendre
On souhaite déterminer pour chaque tâche la date à laquelle elle doit débuter.
On associe à chaque tâche i ϵT une variable de décision ti représentant sa date de début.
On introduit deux tâches fictives : α représentant le début des travaux et ω représentant la fin des travaux. Ces deux tâches ont une durée nulle.
La date de début des travaux correspond à t.
On prend tα = 0, c'est-à-dire que l'origine du temps est fixée à la date de début des travaux.
La date de fin des travaux sera mesurée par tω, date d'exécution de la tâche fictive ω.
Si tα = 0, tω représente aussi la durée des travaux.
Les décisions possibles
Il s'agit de respecter un certain nombre de contraintes portant sur les dates de début des tâches.
Dans le cadre du problème central de l'ordonnancement, on peut prendre en compte, par exemple, les contraintes suivantes :
1 - Contraintes de succession :
La tâche j ne peut commencer avant la fin de i.
2 - Contraintes de succession partielle :
La tâche j peut commencer dès qu'un pourcentage pi de la tâche i est exécuté.
3 - Contraintes de succession immédiate :
La tâche j doit commencer dès que i est terminée.
4 - Date de disponibilité : La tâche i ne peut commencer avant la date ri.
5 - Date de livraison:
La tâche i doit être terminée avant la date li.
Contraintes représentant les décisions possibles :
Les contraintes précédentes ont comme propriété de pouvoir toutes être mises sous la forme :
tj ≥ ti + lij avec i et jϵT et lij un nombre réel.
Cas 1 : tj ≥ ti + di
Cas 2 : tj ≥ ti + pidi
Cas 3 : tj = ti + di soit tj ≥ ti + di et tj ≤ ti + di donc tj ≥ ti + di et ti ≥ tj - di
Cas 4 : ti ≥ ri soit ti ≥ tα + ri (tα = 0)
Cas 5 : ti + di ≤ li soit tα ≥ ti + di-li
Toute contrainte entre les dates de début de tâches qui peut se mettre sous la forme
tj ≥ ti + lij peut être prise en compte dans le cadre du problème central de l'ordonnancement.
Remarque
Parmi les contraintes du problème, il faut introduire celles traduisant que la tâche ω représentant la fin des travaux est postérieure à la fin de toutes les autres.
De même, il faut traduire que les tâches sans prédécesseur ne peuvent commencer ... avant le début.
Le critère
Dans le cadre du problème central de l'ordonnancement, le critère retenu est la recherche d'un ordonnancement conduisant à la durée totale minimale.
Fonction objectif
ω représentant la tâche "fin" du projet, le critère peut être traduit par :
Min (tω) Le problème central de l'ordonnancement est alors modélisé par le problème d'optimisation suivant :
Min (tω),
tj – ti ≥ lij,
tα= 0
A la fin des années 50, des modélisations s'appuyant sur les graphes ont été proposées.
L'une conduit à la méthode PERT (1959 - Program Evaluation Research Task), l'autre à la méthode CPM (1960 - Méthode du chemin critique - Critical Path Method).
Nous développons ici cette dernière. Elle est encore appelée "Méthode des potentiels".
Représentation des données du problème par un graphe : le graphe potentiel-tâche
Les données du problème vont être représentées par un graphe valué, pour lequel il faut définir ce que représentent les sommets, les arcs et les longueurs des arcs.
A chaque tâche de T on associe un sommet du graphe. Le sommet associé à α correspond au début des travaux et le sommet associé à ω correspond à la fin des travaux.
A chaque contrainte on associe un arc :
A la contrainte tj ≥ ti+ lij est associé un arc (i, j) de longueur lij
Le graphe ainsi obtenu porte le nom de graphe potentiel - tâche.
La tâche A n'a a priori pas de prédécesseur mais elle ne peut commencer avant le début des travaux, d'où la contrainte tA ≥ tα représentée par un arc (α, A) de longueur 0. Il en est de même pour B.
La tâche C ne peut commencer avant la fin de A ce qui se traduit par : tC ≥ tA + 7 puisque A à une durée de 7.
Cette contrainte est modélisée par l'arc (A, C) de longueur 7.
Il faut aussi indiquer que la tâche ω ne peut intervenir avant que toutes les tâches ne soient terminées en particulier E et F.
On a, par exemple, tω ≥ tE + 3 contrainte représentée par l'arc (E, ω) de longueur 3.
Résolution du problème
A - Ordonnancement au plus tôt
On construit un premier ordonnancement optimal appelé "ordonnancement au plus tôt".
Définition
On appelle date de début au plus tôt d'une tâche la plus petite date à laquelle elle peut débuter si toutes les contraintes sont respectées.
Le calendrier de l'ensemble des tâches est appelé "ordonnancement au plus tôt".
Soit un graphe associé à un problème d'ordonnancement et soit Cαi "un chemin du sommet α au sommet associé à la tâche i".
Pour tous les arcs (h, k) de ce chemin, on a, par construction, la propriété : tk ≥ th + lhk.
Si on additionne ces inégalités pour tous les arcs du chemin, on arrive à : ti ≥ tα + somme des longueurs des arcs du chemin Cαi
Comme tα = 0, on en déduit que la date de début de la tâche i est au moins égale à la longueur du chemin.
Ce résultat est valable pour tous les chemins de α au sommet i, la date de début au plus tôt de la tâche i est égale à la longueur du plus long chemin de α à i.
Si on prend en particulier le sommet ω associé à la fin des travaux, la date tω qui représente la durée des travaux est au moins égale à la longueur de n'importe quel chemin de α à ω, donc au plus long d'entre eux.
D'où le résultat :
Proposition
La date de début au plus tôt d'une tâche est égale à la longueur du plus long chemin de α au sommet représentant cette tâche dans le graphe potentiel-tâche.
La durée minimale des travaux est égale à la longueur du plus long chemin de α à dans le graphe potentiel-tâche.
Calcul des dates au plus tôt
Ce calcul revient à celui de la longueur d'un plus long chemin. On peut donc utiliser les algorithmes adaptés à la détermination de plus longs chemins.
En particulier, si les seules contraintes sont des contraintes de succession, le graphe potentiel-tâche est sans circuit ; on peut donc utiliser l'algorithme de Bellman.
On prend les sommets dans un ordre tel que chacun n'est examiné qu'après que chacun de ses prédécesseurs a été examiné (tri topologique)
Par application de l'algorithme de Bellman, la date de début au plus tôt ti* de la tâche i est calculée par : ti* = Max( tj* + dj) avec j ϵPred(i)
Par exemple pour le graphe ci-dessus on a :
tE* = Max (tC* + 2, tD*+ 4) = Max (7 + 2, 8 + 4) = 12
B- Ordonnancement au plus tard
Le calendrier précédent conduit à une durée minimale de 15.
Il s’agit maintenant de déterminer la date à laquelle chacune des tâches doit impérativement avoir commencé si on veut que la durée totale des travaux soit respectée.
Définition
On appelle date de début au plus tard d'une tâche la date à laquelle elle doit impérativement avoir commencé afin que la date de fin de travaux soit respectée.
Le calendrier correspondant est l'ordonnancement au plus tard.
Principe de calcul
Sur l'exemple précédent, considérons par exemple la tâche C. Pour déterminer la date à laquelle elle doit impérativement commencer pour que la fin des travaux intervienne à la date 15, il faut s'intéresser à ses deux successeurs E et F.
L'interprétation des arcs du chemin CEω nous indique qu'il faut au minimum 5 unités de temps avant la fin (2 pour C et 3 pour E).
De même, l'interprétation des arcs du chemin CFω indique qu'il faut 2 unités de temps pour C et une unité pour F soit 3 unités de temps.
La tâche F pouvant être faite en parallèle avec E, l'analyse de ces résultats montre qu'il faut au minimum 5 unités de temps après le début de C avant la fin des travaux. Cette durée correspond à la longueur du plus long chemin de C à ω.
Proposition
La date de début au plus tard d'une tâche est égale à la différence entre la date de fin des travaux et la longueur du plus long chemin du sommet représentant cette tâche dans le graphe potentiel-tâche au sommet ω.
Le calcul des dates au plus tard revient donc à un calcul de plus long chemin dans un graphe.
On peut, en s'inspirant des algorithmes développés pour la détermination de plus longs chemins, mettre en place un algorithme permettant d'affecter à chaque sommet une étiquette λ(i) de valeur égale à la longueur du plus long chemin de ce sommet à ω et en déduire la date de début au plus tard, et ceci quelles que soient les propriétés du graphe potentiel-tâche.
Soit Tω la date de fin des travaux.
La date de début au plus tard Ti * d'une tâche i est égale à Tω - longueur du plus long chemin de i à ω.
Ti * = Tω - λ(i).
Il faut donc calculer la longueur λ(i) d'un plus long chemin de i à ω.
Nous allons ici considérer le cas particulier d'un graphe sans circuit et, dans ce cas, établir une formule permettant de déterminer directement les dates de début au plus tard.
Calcul des dates au plus tard dans un graphe sans circuit
Par analogie avec l'algorithme de Bellman pour le calcul de la longueur des plus courts chemins, le calcul de la longueur d'un plus long chemin repose sur le résultat : λ (i) = Max (l(i, j) + λ (j)) le max étant prit sur les successeurs de i et λ(j) étant égal à la longueur d'un plus long chemin de j à ω.
On a donc :
Ti * = Tω - λ (i) = Tω - Max (l(i, j) + λ (j)) = Min(Tω - λ (j) - l(i, j)), le min étant pris sur les successeurs j de i. d'où le résultat :
Ti * = Min (Tj* - l(i,j)) le min étant pris sur les successeurs j de i.
Exemple :
Les tâches sont examinées dans l'ordre suivant :
Tω = 15, TE* = 12 ou TF* = 14, TC* = 10 ou TD* = 8, TA* = 1 ou TB* = 0, Tα = 0
Par exemple, pour D on calcule :
Min(TE* - l(D, E), TF* - l(D, F)) = Min(12 - 4, 14 - 4) = 8
Ce tableau récapitule les 2 calendriers particuliers, ordonnancement au plus tôt et au plus tard, conduisant à
la durée totale minimale de 15.
C - Tâches critiques, chemin critique
Dans l’exemple précédent, la tâche D a une date de début au plus tôt égale à sa date de début au plus tard :
la date de début est donc impérative si on veut que les travaux soient réalisés dans une durée minimale.
Définition
Une tâche critique est une tâche dont les dates de début au plus tôt et au plus tard coïncident.
Tout retard sur les tâches critiques retarde la fin des travaux.
Définition
La marge totale d'une tâche est égale à la différence entre la date début au plus tard et la date de début au
plus tôt.
Les tâches critiques sont donc les tâches de marge totale nulle.
Exemple
Les tâches critiques sont ici α, B, D, E et ω.
Ces tâches critiques sont situées sur le chemin α B D E ω de longueur 15 qui est le plus long chemin de
α à ω.
Définition
Le chemin critique est le plus long chemin du sommet "début" au sommet "fin".
Proposition
Les sommets du chemin critique sont les tâches critiques.
E- Marge libre
Toutes les tâches non-critiques ne sont pas équivalentes.
Parmi les tâches non-critiques, il en existe qui, si elles ne commencent pas à leur date au plus tôt, les
suivantes ne peuvent pas non plus commencer à leur date au plus tôt. On dira que leur marge libre est nulle.
Définition
La marge libre d'une tâche est le délai dont on dispose pour la retarder par rapport à sa date au plus tôt, en
laissant la possibilité aux suivantes de commencer au plus tôt.
Marge libre de i = min (t j* - l(i, j) - t i*) pour jϵ succ(i) Exemple :
Sur cet exemple, on connaît les dates au plus tôt des 3 tâches i, j, k.
On peut retarder i de 2 par rapport à sa date au plus tôt, tout en permettant à j de commencer à la date
10 et à k de commencer à la date 11.
L'ensemble des résultats est regroupé dans le tableau ci-dessous :
