Ordonnancement de projet à ressources illimitées puis limitées
Première partie : les moyens sont supposés illimités
On considère un problème d'ordonnancement de projet dont le graphe de précédence entre les tâches et la durée des tâches (en jours) sont donnés par le graphe ainsi que le tableau ci-dessous.
Une tâche ne peut commencer que si la tâche précédente est entièrement terminée.
Le projet doit être effectué en 60 jours au plus.
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Durée de la tâche i | 10 | 10 | 10 | 8 | 7 | 10 | 12 | 9 | 13 | 5 | 2 | 4 | 0 |
Question
On vous demande de calculer pour ce problème : les dates de début au plus tôt ASAP(i) d'exécution des tâches en démarrant la tâche 1 à l'instant 0 et les dates de début au plus tard ALAP60(i) des tâches de manière à terminer la tâche 12 à la fin du 60 ième jour.
Dates au plus tôt et dates au plus tard
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Dates au plus tôt ASAP(i) | 0 | 10 | 20 | 44 | 10 | 17 | 32 | 10 | 19 | 32 | 37 | 52 | 56 |
Dates au plus tard ALAP60(i) | 4 | 28 | 38 | 48 | 19 | 26 | 36 | 14 | 23 | 49 | 54 | 56 | 60 |
Après avoir examiné les résultats de la question précédente et voulant respecter la stratégie suivante : ne pas commencer trop tôt les tâches de début de projet de manière à sortir des fonds de la trésorerie le plus tard possible, mais planifier un peu avant leur date au plus tard les tâches de la dernière partie de manière à se prémunir contre des aléas possibles, le chef de chantier propose le calendrier suivant pour les dates de début des tâches :
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
e(i) | 2 | 26 | 37 | 46 | 12 | 20 | 34 | 12 | 21 | 46 | 50 | 55 | 60 |
Question
Ces dates de début de tâches sont refusées par le chef de projet.
On vous demande d'expliciter toutes les raisons qui lui font rejeter cette proposition.
On peut aisément vérifier que l'ordonnancement proposé est compris entre les dates au plus tôt et les dates au plus tard pour terminer à l'instant 60, mais cela n'est pas suffisant, il faut également vérifier que toutes les contraintes de précédence sont vérifiées entre les tâches et cela n'est pas le cas par deux fois :
- entre les tâches 3 et 4 : e(3) + d(3) = 37 + 10 = 47 > 46 = e(4)
- entre les tâches 10 et 11 : e(10) + d(10) = 46 + 5 = 51 > 50 = e(11)
Après discussion et prise en compte de contraintes extérieures non explicitées dans le modèle, le chef de chantier et le chef du projet se mettent d'accord sur les dates de début de tâches suivantes :
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
t(i) | 2 | 12 | 23 | 46 | 12 | 20 | 34 | 12 | 21 | 45 | 50 | 55 | 60 |
Question
Pourquoi le chef de projet est-il d'accord avec ce nouveau planning ?
On peut aisément vérifier que l'ordonnancement proposé est compris entre les dates au plus tôt et les dates au plus tard pour terminer à l'instant 60 et cette fois, les contraintes de précédence entre les tâches sont toutes vérifiées (la meilleure preuve en est qu'à la question suivante on obtiendra bien des marges libres à droite positive ou nulle).
Question
Pour l'ordonnancement défini par les dates de début de tâches t(i), on vous demande de calculer : les marges totales (pour terminer en 60) et les marges libres à droite.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
MT(i) | 2 | 16 | 15 | 2 | 7 | 6 | 2 | 2 | 2 | 4 | 4 | 1 | 0 |
mld(i) | 0 | 1 | 13 | 1 | 1 | 4 | 0 | 0 | 0 | 0 | 3 | 1 | 0 |
Deuxième partie : les ressources humaines sont limitées
Chaque tâche nécessite la présence de personnel polyvalent pour ce type de tâche, mais dont le nombre dépend de la tâche. Le nombre de personnes nécessaire pour exécuter la tâche i durant toute la durée de la tâche est fourni par le tableau suivant :
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Nombre de personnes | 1 | 2 | 2 | 4 | 1 | 1 | 3 | 2 | 3 | 2 | 4 | 1 | 0 |
Question
On vous demande simplement de dessiner, pour l'ordonnancement défini par les dates de début de tâches t(i), la courbe des demandes instantanées de personnel nécessaire à l'exécution des tâches se déroulant à chaque instant.
On constate qu'il faut 8 personnes entre les instants 50 et 52.
Question
On vous demande de fournir :
- le nombre moyen de personnes nécessaires au cours du temps sur la durée de tout ordonnancement lorsque le projet ne prend pas de retard (moyenne des demandes en ressources sur l'intervalle [0, 60]) de 60 unités de temps,
- de déduire de la question précédente un majorant pour le nombre maximal de personnes nécessaires en un même instant.
Le nombre moyen de personnes nécessaires au cours du temps sur la durée de l'ordonnancement est :
Nmoy = (10x1+10x2+10x2+8x4+7x1+10x1+12x3+9x2+13x3+5x2+2x4+4x1)/60 = 3,56
Un majorant du nombre maximal de personnes nécessaires en un même instant correspond au maximum de la courbe de ressources de la question précédente :
majorant de Nmax = 8.
Ce pourrait être moins, si on avait essayé d'autres ordonnancements.
Pour le majorant, on prend toujours la plus petite valeur obtenue pour le nombre maximal de personnes de toutes les solutions examinées.
On cherche à terminer à l'instant 60 tout en minimisant le nombre maximal de personnes nécessaires en un même instant.
Pour obtenir un minorant de ce nombre maximal, on utilise la technique des parties obligatoires.
Définition :
la partie obligatoire de la tâche i est la partie comprise entre sa date au plus tard de début ALAP60(i) et sa date au plus tôt de fin ASAP(i) augmentée de la durée de de la tâche d(i).
La partie obligatoire d'une tâche n'existe que si la ALAP60(i) est inférieure ou égale àASAP(i)+d(i).
Les ressources demandées par la tâche i sont absolument nécessaires sur l'intervalle défini par cette partie obligatoire.
Si la durée de cette partie obligatoire est de 0, on en a besoin juste avant ou juste après.
Question
On vous demande de dessiner la courbe cumulée des demandes de ressources correspondant aux seules parties obligatoires et d'en déduire un minorant du nombre maximal de personnes nécessaires.
Beaucoup de tâches n'ont pas de parties obligatoires.
On trouve ici la valeur 4 comme minorant de Nmax.
On n'a pas réussi à améliorer un minorant que nous connaissions déjà (le nombre maximal de personnes demandées par une tâche).
On ne peut donc rien conclure de plus.
La solution minimale est entre le minorant 4 et le majorant 8.
Le problème d'ordonnancement de projet avec contraintes cumulatives est très difficile à résoudre.
Il y a donc eu de très nombreux algorithmes exacts, de type procédure par séparation et évaluation (voir le module sur les méthodes exactes) qui ont été proposés et testés pour le résoudre en essayant d'obtenir la solution optimale dans un temps raisonnable (ou à défaut une très bonne solution si on interrompt l'algorithme avant sa fin).
Il est hors de question ici de présenter l'un de ses algorithmes.
Nous proposons simplement une approche intuitive qui montre comment on pourrait construire une procédure par séparation et évaluation (pas forcément des plus efficaces) pour résoudre ce problème.
Question
Expliquer comment à partir des outils utilisés dans les questions précédentes, on pourrait construire une procédure par séparation et évaluation pour résoudre de manière optimale le problème de l'ordonnancement de projet avec une ressource en quantité limitée de manière à minimiser le nombre maximal de ressources demandées.
Corrigé rapide :
On commence avec un nœud racine Ao de l'arborescence, pour lequel toutes les solutions du problème sont possibles.
Son minorant bo est celui calculé précédemment avec les parties obligatoires.
La valeur de la meilleure solution réalisable trouvée BEST est donnée, par exemple, par le minimum entre le nombre maximal de personnes obtenu pour l'ordonnancement au plus tôt et pour l'ordonnancement au plus tard en utilisant leur courbe cumulée de demandes de ressources.
Par la suite :
En chaque noeud de l'arborescence Ai, on est capable d'obtenir un minorant du sous-ensemble bi en calculant le maximum de ressources demandé par les parties obligatoires compte tenu des décisions déjà prises pour Ai.
On peut également améliorer le majorant BEST (meilleure solution réalisable obtenue en complétant la solution partielle au plus tôt et au plus tard compte tenu des décisions prises).
Un ensemble Ai est éliminé de l'exploration par l'utilisation classique des majorants et des minorants dans les PSE (un ensemble est éliminé quand son minorant bi est supérieur ou égal à la meilleure solution réalisable trouvée).
Tout ensemble non éliminé est séparé en choisissant une tâche k pour laquelle la partie obligatoire n'est pas encore égale à la durée de la tâche et en la plaçant dans toutes les positions encore permises compte tenu des décisions déjà prises.
Pour chaque sous-ensemble créé par la séparation, la tâche k est placée de manière définitive à une date donnée.
Placer une tâche à une date donnée augmente les parties obligatoires des tâches qui la précèdent si on la place tôt dans l'ordonnancement et/ou des tâches qui la suivent si on la place tard dans l'ordonnancement.
Après le placement, l'ordonnancement est donc plus précis, les parties obligatoires plus importantes et le minorant peut avoir été augmenté.
Comme dans toute procédure par séparation et évaluation, la méthode s'arrête lorsqu'il n'y a plus de nœud dans l'arborescence et la solution à retenir est la meilleure solution trouvée.
Cette méthode est bien sûre excessivement chronophage, elle vous est simplement présentée pour vous donner un exemple de méthode exacte utilisant une procédure par séparation et évaluation.
