Différents problèmes d'ordonnancement de projet avec ressources limitées
Nous supposons maintenant que les ressources humaines sont disponibles en quantité limité pour réaliser la recette de la paella.
Pour un ordonnancement o donné, il convient de vérifier si le nombre total de ressources humaines nécessaires à l'instant t est bien inférieur ou égal au nombre de ressources disponibles.
Zoom sur le diagramme de Gantt de l'ordonnancement au plus tard de la paella
Nous avons limité le diagramme de Gantt à l'intervalle de temps compris entre les instants 46 et 62.
Nous n'avons représenté sur ce diagramme de Gantt que les tâches qui demandaient une personne pour être réalisée (la tâche numérotée 6 correspond en fait à la sous-tâche 6.6, la sous-tâché 6.5 qui la précède immédiatement ne nécessite pas de ressource humaine.
Il est à noter qu'entre les instants 57 et 58, on a besoin simultanément de 8 personnes pour pouvoir réaliser la recette au plus tard. Les couleurs utilisées correspondent aux tâches que l'on peut, par exemple, confier à une même personne, on voit qu'il a fallu utiliser 8 couleurs entre les instants 7 et 8.
Définition : Courbe de cumul des ressources
La courbe de cumul des ressources nécessaires est égal au nombre de ressources nécessaires à chaque instant pour réaliser l'ensemble des tâches qui sont actives.
La courbe de cumul des ressources disponibles est égal au nombre de ressources effectivement présentes à chaque instant.
Fondamental :
Un ordonnancement de projet à ressources limitées est réalisable
s'il respecte les contraintes de précédence,
si la courbe de cumul des ressources nécessaires est toujours inférieure ou égale à la courbe de cumul des ressources disponibles.
Cas particulier où il n'y a qu'une seule ressource disponible à chaque instant
Pour la paella, c'est le cas où une ménagère est seule chez elle pour réaliser la paella.
Dans le bâtiment, ce peut être le cas où la plupart des moyens matériels existent en quantité suffisante, sauf une grue qui n'existe qu'en un seul exemplaire. Dans le projet qui consiste à construire une maison ou un building ou une usine, les tâches qui utilisent la grue ne peuvent pas être exécuter en parallèle alors qu'il n'y a pas de problème de ressources pour les autres tâches.
Dans un atelier, c'est le cas où on utilise de nombreux petits outils et des ressources humaines en quantités suffisantes, mais une unique machine permet de faire une opération mécanique ou chimique, par exemple, importante. Seules les opérations qui passent sur la machine doivent être ordonnancées, alors que les opérations qui ne passent pas sur la machine correspondent seulement à des contraintes de précédence qui induisent des intervalles de temps entre les opérations qui passent sur la machine.
Définition : Ordonnancements disjonctifs
Lorsque, dans un problème d'ordonnancement, il existe une seule ressource et que cette ressource existe en un seul exemplaire, l'ordonnancement est qualifié de disjonctif.
Définition : Graphes disjonctifs
Un graphe disjonctif est un graphe (X,E,D) où
X est un ensemble de points
E est un ensemble d'arcs conjonctifs
Tous les arcs conjonctifs de E existent obligatoirement.
D est un ensemble d'arcs disjonctifs où les deux arcs (x,y) et (y,x) sont mis en disjonction,
c'est à dire que
ou bien (x,y) existe et (y,x) n'existe pas
ou bien (y,x) existe et (x,y) n'existe pas
Définition : Graphes valués disjonctifs
Dans un graphe disjonctif valué (X,E, VE, D, VD),
à chaque arc conjonctif correspond une valeur VE(x,y),
à chaque arc disjonctif correspond deux valeurs VD(x,y) et VD(y,x) qui peuvent être égales ou différentes.
Représentation graphique des arcs disjonctifs
Les arcs conjonctifs correspondent ici à la tâche 1 (de durée 3) qui précède les tâches 2 et 4. La tâche 2 (de durée 5) précède la tâche 3. La tâche 4 (de durée 2) précède la tâche 5. La tâche 6 est la tâche fictive de fin de l'ordonnancement de projet.
Les tâches 2, 4 et 5 utilisent une ressource qui n'existe qu'en un seul exemplaire. Aussi, ou bien la tâche 2 précède la tâche 3, ou bien la tâche 3 précède la tâche 2. Il en est de même pour les tâches 2 et 5. Par contre, comme il existe une contrainte de précédence entre les tâches 4 et 5, cet arc conjonctif élimine la possibilité de disjonction entre les deux tâches.
La valeur sur les arcs disjonctifs est égal à la durée de la tâche qui se trouve à l'origine de l'arc dans chaque sens possible pour la disjonction.
Les arcs disjonctifs ont été ici dessinés en rouge. Ils sont représentés par des petits "papillons" correspondant à deux triangles mis en opposition.
Cas général : une ou plusieurs ressources existent en plusieurs exemplaires
On parle alors d'ordonnancement à contraintes cumulatives.
Différentes hypothèses peuvent préciser le nombre de ressources et pour chaque ressource, un nombre d'exemplaires de la ressources constant au cours du temps ou au contraire variable au cours du temps selon une courbe de disponibilité donnée comme contrainte a priori.
Remarque :
L'exercice proposé à la fin de ce chapitre donne un exemple de ce type de problème.
Il s'agit de problèmes d'ordonnancement très difficiles, bien au delà des algorithmes de graphe que nous présentons dans ce module.
