Heuristiques simples sur la paella avec une seule ressource humaine
Ordonnancement sans délai à règle de priorité / cas disjonctif
Une seule personne va réaliser la paella.
On a donc un ordonnancement de projet disjonctif pour lequel on souhaite utiliser des heuristiques à règle de priorité.
Question
Réécrire le générateur d'ordonnancement sans délai dans le cas où il n'y a qu'une seule ressource en un seul exemplaire.
Décrire le problème simplifié avec les notations qui correspondent aux données du problème.
et fournir les notations simplifiées utiles pour l'algorithme :
on n'a plus besoin d'indice pour les ressources,
on n'a plus besoin du nombre de ressources disponibles à tout instant,
on complète simplement en permanence sur la ressource humaine l'ordonnancement par sa fin.
on place en parallèle toutes les tâches qui n'utilisent pas la ressource au fur et à mesure où les prédécesseurs sont placés.
Fournir ensuite l'ordonnancement détaillé (même niveau de détail que précédemment).
Notation pour le générateur d'ordonnancement sans délai pour un ordonnancement disjonctif
Soit N un ensemble de N tâches numérotées de 1 à n.
Soit d(i) la durée de la tâche i.
Soit r(i) qui vaut 0 pour les tâches qui n'utilisent pas la ressource et 1 lorsque la ressource qui existe en un seul exemplaire est utilisée.
Soit (N, P, A) le graphe valué de n sommets où P correspond à des contraintes de précédence entre des couples de tâches et où A correspond à la durée minimale à attendre entre le début des deux tâches du couple de P.
On cherche à exécuter l'ensemble des tâches tout en respectant les contraintes de précédence et les contraintes de ressources tout en minimisant la durée totale de l'ordonnancement.
t est l'indice temporel que l'on initialise à 0 et qui progresse au cours de l'algorithme.
D est l'ensemble des tâches disponibles, c'est-à-dire dont tous les tâches qui précèdent sont déjà placées.
trd est la date à partir de laquelle la ressource devient disponible après la dernière tâche placée sur cette ressource, on aura toujours trd supérieur ou égal à t.
td(i) est la date choisie pour le début de la tâche i ou -1 quand la tâche n'est pas encore placée.
PRIO(i) est la priorité de la tâche i.
ASAP(i) est une fonction qui calcule la date au plus tôt à partir de laquelle on peut placer une tâche de D, c'est le calcul classique de la date au plus tôt pour les tâches qui n'utilise pas la ressource, c'est le maximum entre la date au plus tôt et trd pour les tâches qui utilisent la ressource.
ASAPmin et la plus petite date au plus tôt où on peut placer une tâche de D.
Description du générateur d'ordonnancement sans délai pour un ordonnancement disjonctif
Initialisation
D = l'ensemble des tâches de D sans prédécesseur ;
ASAP(0)=0 ;
trd=0 ;
pour tout i : td(i)=-1 ;
td(0)=0 ;
k=0 ;
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Placement des n tâches
tant que k < n faire
-------------------------------------------------------------------------------------
Placement des tâches sans prédécesseur qui n'utilisent pas la ressource
tant que il existe i sans prédécesseur et non placé qui n'utilise pas la ressource faire
td(i)=ASAP(i) ;
k=k+1 ;
fin tanque
-------------------------------------------------------------------------------------
si k < n faire
Calcul de ASAPmin
ASAPmin=+∞ ;
pour tout i de 1 à n faire
si td(i) = - 1 alors
si toutes les tâches prédécesseur de i sont placées alors
si ASAP(i)<ASAPmin alors ASAPmin=ASAP(i) finsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'est pas encore placée
fin pour tout i ;
-------------------------------------------------------------------------------------
recherche de la tâche la plus prioritaire
qui peut démarrer à l'instant ASAPmin
PRIOmax=-1 ; imax=-1 ;
pour tout i de 1 à n faire
si td(i) = - 1 alors
si toutes les tâches prédécesseur de i sont placées alors
si ASAP(i)=ASAPmin et PRIO(i)>PRIOmaxalors PRIOmax=PRIO(i) et imax = ifinsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'est pas encore placée
fin pour tout i ;
-------------------------------------------------------------------------------------
placement de la tâche imax
td(imax)=ASAPmin ;
trd=ASAPmin+td(imax) ;
-------------------------------------------------------------------------------------
k=k+1 ;
finsi k < n
fin tant que
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Choix d'une règle de priorité
On se donne ici une règle de priorité statique à partir des marges totales de l'ordonnancement au plus tôt de l'ordonnancement de projet à ressources illimitées et des durées des tâches.
Lorsque l'on compare la priorité de deux tâches,
la tâche la plus prioritaire est celle de plus petite marge totale
à égalité celle de plus petite durée
à égalité, par exemple, de manière arbitraire celle de plus petit numéro.
Rappel des dates au plus tôt, au plus tard et des marges totales sur le problème de la paella
Les tâches coloriées en jaune nécessitent une ressource humaine pour leur exécution.
La tâche 6 est en jaune pâle car c'est une tâche composée de 7 petites tâches où les tâches 6.3 et 6.5 n'ont pas besoin de ressource humaine.
Question
Appliquer le générateur d'ordonnancement sans délai avec cette règle de priorité pour obtenir un ordonnancement réalisable de la préparation d'une paella lorsque l'on n'a qu'une seule personne pour réaliser la recette.
Le calcul de ASAP(i) est beaucoup plus facile à calculer que dans le cas général de l'ordonnancement cumulatif.
En effet, c'est la date au plus tôt pour les tâches qui n'utilisent pas la ressource.
C'est le maximum entre trd est la date au plus tôt pour les tâches qui utilisent la ressource.
On pourrait donner comme réponse le tableau des d(i).
Mais on voit beaucoup mieux la solution en la présentant sous forme d'un diagramme de Gantt où on utilise deux couleurs, une pour les tâches qui n'utilisent pas la ressource et une pour les tâches qui utilisent la ressource.
En fait, pour les tâches qui utilisent la ressource, on va alterner le bleu foncé et le bleu ciel de manière à ce que les changements de tâches soient plus visibles sur le diagramme.
La tâche 6 est séparée en 7 parties :
La tâche 6.0 de durée 5 qui utilise la ressource.
La tâche 6.1 de durée 1 qui utilise la ressource.
La tâche 6.2 de durée 1 qui utilise la ressource.
La tâche 6.3 de durée 28 qui n'utilise pas la ressource.
La tâche 6.4 de durée 2 qui utilise la ressource.
La tâche 6.5 de durée 10 qui n'utilise pas la ressource.
La tâche 6.6 de durée 3 qui utilise la ressource.
Soit une durée totale de 50 minutes comme utilisée dans le calcul des dates au plus tôt et au plus tard.
Ordonnancement sans délai construit par une heuristique pour la paella
On voit ici que l'on place la tâche 6.4 est retardée car on a placé la tâche la plus prioritaire 16 de durée 5 pour ne pas créer d'inactivité de la ressource juste avant l'arrivée de la tâche 6.4.
De même la tâche 6.6 est retardée car on a placé la tâche la plus prioritaire 10 de durée 5 pour ne pas créer d'inactivité de la ressource juste avant l'arrivée de la tâche 6.6. Comme à partir de 7, le chemin est critique, cela retarde au total de 5 unités la fin de l'ordonnancement.
Question
Réécrire le générateur d'ordonnancement sans délai dans le cas où il n'y a qu'une seule ressource en un seul exemplaire.
Les mêmes que pour l'ordonnancement sans délai.
Description du générateur d'ordonnancement actif pour un ordonnancement disjonctif
Initialisation
D = l'ensemble des tâches de D sans prédécesseur ;
ASAP(0)=0 ;
trd=0 ;
pour tout i : td(i)=-1 ;
td(0)=0 ;
k=0 ;
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Placement des n tâches
tant que k < n faire
-------------------------------------------------------------------------------------
Placement des tâches sans prédécesseur qui n'utilisent pas la ressource
tant que il existe i sans prédécesseur et non placé qui n'utilise pas ressource faire
td(i)=ASAP(i) ;
k=k+1 ;
fin tanque
-------------------------------------------------------------------------------------
si k < n faire
Calcul de ASAPmin et FINmin
ASAPmin=+∞ ;
FINmin=+∞ ;
pour tout i de 1 à n faire
si td(i) = - 1 alors
si toutes les tâches prédécesseur de i sont placées alors
si ASAP(i)+d(i)<FINmin alorsFINmin=ASAP(i)+d(i) finsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'est pas encore placée
fin pour tout i
-------------------------------------------------------------------------------------
recherche de la tâche la plus prioritaire
qui peut démarrer strictement avant l'instant FINmin
PRIOmax=-1 ; imax=-1 ;
pour tout i de 1 à n faire
si td(i) = - 1 alors
si toutes les tâches prédécesseur de i sont placées alors
si ASAP(i)<FINmin et PRIO(i)>PRIOmaxalors PRIOmax=PRIO(i) et imax = ifinsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'est pas encore placée
fin pour tout i
-------------------------------------------------------------------------------------
placement de la tâche imax
td(imax)=ASAP(imax) ;
trd=ASAP(imax)+td(imax) ;
-------------------------------------------------------------------------------------
t=ASAPmin ;
k=k+1 ;
finsi k < n
fin tant que
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Question
Appliquer le générateur d'ordonnancement actif avec cette règle de priorité pour obtenir un ordonnancement réalisable de la préparation d'une paella lorsque l'on n'a qu'une seule personne pour réaliser la recette.
Ordonnancement actif construit par une heuristique pour la paella
On voit ici que la tâche 6.4 la plus prioritaire n'a pas été retardée, mais néanmoins, on a placé devant la tâche la plus prioritaire 13 de durée 2, pour ne pas laisser la machine totalement inoccupée (il n'y avait pas de tâche de durée 3 qui aurait idéalement occupé l'espace.
De même la tache 6.6 la plus prioritaire n'a pas été retardée, mais la tâche 12 est venue compléter les tâches 16 et 17 de manière à occuper l'espace disponible avant la tâche la plus prioritaire.
Néanmoins, le chemin critique est allongé de 3 unités de temps, c'est dû aux tâches 11 (de durée 2) et 14 (de durée 1) qui n'avaient pas encore été placées sur la ressource et qui doivent l'être avant de pouvoir exécuter la tâche 19.
Remise en question de la modélisation de la tâche 6
Sauf si le fait de laisser refroidir le court bouillon le rend meilleur, on constate ici qu'entre la tâche 6.4 et la tâche 6.6, on consacre 10 minutes à laisser refroidir le court bouillon pour ensuite le réchauffer. Aussi, pourrait-on supprimer la tâche 6.5, voire la tâche 6.6 si le court bouillon est utilisé juste après avoir été préparé. Néanmoins, la présence de cet intervalle de refroidissement a rendu plus intéressant l'utilisation des générateurs d'ordonnancement sans délai et actif.
