Méthodes approchées simples pour les ordonnancements à ressources limitées
Hypothèse
Pour simplifier la présentation, nous considérons ici que nous devons trouver une solution réalisable du problème considéré qui minimise un critère donné.
Dans le cas de la paella, lorsque l'on se donne un nombre maximal de personnes pour réaliser la paella, le critère à minimiser sera la durée totale de l'ordonnancement de manière à commencer la recette le plus tard possible.
En ordonnancement, la durée totale est aussi appelée makespan, mais nous conserverons ici le terme durée totale.
Définition : Minorant
Etant donné,
un problème π ;
l'ensemble S des solutions réalisables du problème π ;
C(s) la valeur du critère à minimiser pour la solution s de S ;
Min est un minorant de la solution optimale s* du problème π si et seulement si ∀s ∈ S : Min ≤ C(s)
Définition : Heuristique
On appelle heuristique une méthode de résolution qui ne permet pas d'affirmer que le résultat obtenu est toujours optimal.
Remarque :
Il est souvent plus facile de trouver un minorant de la solution minimale d'un problème que de trouver la solution minimale.
Par exemple, la durée totale du problème d'ordonnancement à moyen illimité est un minorant de la durée totale du problème d'ordonnancement à moyen limité.
Si on a la chance de trouver une solution réalisable so qui est égale à un minorant Min de la solution optimale, alors cette solution réalisable est elle-même optimale. En effet, on a : C(so) = Min ≤ C(s), ∀s.
Il est donc très intéressant de trouver des minorants les plus proches possibles de la solution optimale (voire égaux à la solution optimale dans le cas idéal).
Heuristiques d'ordonnancement à base de règles de priorité
Ce sont les heuristiques les plus anciennes et les plus simples utilisés pour obtenir des solutions réalisables pour des problèmes d'ordonnancement (sans avoir de garantie sur l'optimalité de la solution trouvée).
Ce sont des algorithmes dits gloutons ou gourmands, dans lesquels on place une tâche à chaque itération et on ne remet jamais en cause le placement des tâches fait aux itérations précédentes.
La règle de priorité permet de décider dans quel ordre on considère les tâches.
Plusieurs tâches peuvent avoir la même priorité.
La règle de priorité est dite statique si on calcule a priori les priorités associées à toutes les tâches et qu'elles ne changent pas au fur et à mesure des itérations, elle est dite dynamique dans le cas contraire où on recalcule les priorités au fur et à mesure de la construction de la solution.
A chaque itération, on cherche à placer une tâche de la manière la plus intelligente possible.
Chaque règle de priorité et chaque règle de placement des tâches conduit à une heuristique différente.
Comme ces heuristiques sont extrêmement rapides, on peut en appliquer plusieurs et retenir la meilleure des solutions réalisables obtenues.
En ordonnancement, à partir d'une règle de priorité, on peut choisir la tâche à placer de deux manières différentes selon le mode de placement retenu, cela donne soit des ordonnancements sans délai, soit des ordonnancements actifs.
Définition : Ordonnancement semi-actif ou calé à gauche
Un ordonnancement est semi-actif ou calé à gauche si toute tâche est calée à gauche, soit sur ses contraintes de précédence, soit sur au moins une tâche qui la précède sur les ressources qu'elle utilise.
Exemple d'ordonnancements semi-actifs ou calés à gauche
La tâche 7 est calée à gauche sur ses contraintes de précédence (tâches 5 et 6).
La tâche 7 est calé à gauche sur la tâche qui la précède sur la ressource.
Définition : Ordonnancement sans délai
Un ordonnancement est sans délai si on ne laisse pas une ressource inoccupée pendant un intervalle de temps alors qu'une tâche est en attente au début de l'intervalle pour être exécutée sur cette ressource (et qu'aucune autre contrainte n'interdit son exécution).
Illustration d'ordonnancements sans délai
Les ordonnancements calés gauche précédent étaient sans délai, avec l'hypothèse que la tâche 7 suit les tâches 5 et 6.
L'ordonnancement ci-dessus n'est pas sans délai, car la machine est laissée inoccupée avant la tâche 3 alors que la tâche 7 est déjà disponible dès que 5 est terminée.
Remarque :
Un ordonnancement sans délai est toujours calé à gauche alors qu'un ordonnancement calé à gauche n'est pas toujours sans délai. Par exemple, dans un ordonnancement calé à gauche, il peut y avoir un intervalle où la ressource n'est pas utilisée parce qu'une tâche est calé sur une contrainte de précédence alors qu'une tâche placée derrière elle sur la même ressource aurait pu être placée devant elle.
Définition : Ordonnancement actif
Un ordonnancement est actif s'il est calé à gauche et s'il ne contient pas d'intervalle où une ressource est inoccupée alors qu'une tâche exécutée plus tard pourrait être placée dans cet intervalle sans modifier l'ordonnancement d'aucune des autres tâches qui suivent l'intervalle dans l'ordonnancement.
Illustration d'ordonnancements actifs
Toujours avec l'hypothèse que 7 suit les tâches 5 et 6, l'ordonnancement ci-dessus est actif, car la machine reste bien inoccupée devant la tâche 3, mais la durée de l'intervalle compris entre la fin de 5 et le début de 3 n'est pas suffisante pour pouvoir y placer la tâche 7 sans reculer la tâche 3.
Toujours avec l'hypothèse que 7 suit les tâches 5 et 6, l'ordonnancement ci-dessus n'est pas actif, car la machine reste inoccupée devant la tâche 3, alors que la durée de l'intervalle compris entre la fin de 5 et le début de 3 est suffisante pour pouvoir y placer la tâche 7 sans reculer la tâche 3.
Remarque :
Un ordonnancement sans délai est obligatoirement actif alors qu'un ordonnancement actif peut ne pas être sans délai (si les intervalles où les ressources sont inoccupées sont trop petits pour placer les tâches qui sont placées ultérieurement).
Remarque :
Pour un problème d'ordonnancement donné,
l'ensemble des solutions réalisables contient l'ensemble des solutions semi-actives ou calées à gauche,
l'ensemble des solutions semi-actives ou calées à gauche contient l'ensemble des solutions actives,
l'ensemble des solutions actives contient l'ensemble des solutions sans délais.
Définition :
Pour un problème donné, un sous-ensemble de solutions est dit dominant s'il contient au moins une solution optimale.
Il peut y avoir des solutions optimales à l'extérieur de l'ensemble dominant, mais il doit y avoir au minimum une solution optimale à l'intérieur de l'ensemble dominant.
Remarque :
Si l'on cherche une seule solution optimale et non pas toutes les solutions optimales, on peut se contenter d'explorer les ensembles dominants, ce qui réduit souvent la durée de la recherche de la solution optimale surtout lorsque les problèmes sont difficiles à résoudre.
Définition :
En ordonnancement, un critère à minimiser est dit régulier, si on ne peut pas augmenter sa valeur (et donc diminuer sa qualité) en diminuant la date de début d'une des tâches sans toucher aux autres tâches.
Remarque :
La durée totale d'un ordonnancement est un critère régulier.
Fondamental :
L'ensemble des ordonnancements calées à gauche est dominant pour tout critère régulier.
L'ensemble des ordonnancements actifs est dominant pour tout critère régulier.
L'ensemble des ordonnancements sans délais n'est pas dominant, c'est à dire que la solution optimale peut ne pas être sans délai.
Il se peut qu'il existe une solution optimale sans délai, mais ce n'est pas toujours le cas.
Remarque :
Bien que l'ensemble des ordonnancements sans délai ne soit pas dominant, quand on n'utilise que des heuristiques, il est possible que l'heuristique qui construit des ordonnancements sans délai donne de meilleures solutions que l'heuristique qui construit des ordonnancements actifs. Sur un jeu de données, c'est une heuristique qui sera la meilleure alors que sur un autre jeu de données ce sera le contraire.
Générateur d'ordonnancement : définition du problème d'ordonnancement de projet cumulatif
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 un ensemble de ressources numérotées de 1 à r.
Soit nrd(j) le nombre d'exemplaires disponibles à tout instant de la ressource j.
Soit nrn(i,j) le nombre d'exemplaires de la ressource j nécessaires pour exécuter la tâche i.
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.
Générateur d'ordonnancement sans délai : notations pour l'algorithme
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.
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, compte tenu de l'occupation des ressources par les tâches déjà placées (l'algorithme de cette fonction n'est pas décrit ici, mais toutes les informations sont disponibles pour l'écrire).
ASAPmin et la plus petite date au plus tôt où on peut placer une tâche de D.
CUMUL(j,v) est le nombre d'unité de la ressource j occupée à l'instant v et l'intant v+1.
Générateur d'ordonnancement sans délai : algorithme
Initialisation
t = 0;
D = l'ensemble des tâches de D sans prédécesseur ;
pour tout j faire trd(j) = t fin pour j;
pour tout i faire td(i) = -1 fin pour i;
pour tout j et pour tout v faire CUMUL(j,v) = 0 fin pour tout j et tout v;
k = 0;
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Placement des n tâches
tant que k < n faire
------------------------------------------------------
Placement des tâches sans prédécesseur qui n'utilisent aucune ressource
tant que il existe i sans prédécesseur et non placé qui n'utilise aucune 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'était 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)>PRIOmax alors
PRIOmax=PRIO(i);
imax = ifinsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'était pas encore placée
fin pour tout i;
-------------------------------------------------------------
placement de la tâche imax
td(imax)=ASAPmin;
pour j de 1 à r faire
pour v de ASAPmin à ASAPmin+d(imax)-1 faire
CUMUL(j,v)=CUMUL(j,v)+nrn(imax,j) ;
fin pour v;
fin pour j;
--------------------------------------------------------------
t=ASAPmin;
k=k+1;
finsi k < n
fin tant que k < n
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Générateur d'ordonnancement actif : notations nouvelles
FINmin va être la date de fin au plus tôt d'une tâche non encore placée dont tous les prédécesseurs ont déjà été placés.
Si la tâche placée ne commençait pas strictement avant FINmin, on créerait un ordonnancement non actif.
Générateur d'ordonnancement actif : algorithme
Initialisation
t=0;
D = l'ensemble des tâches de D sans prédécesseur;
pour tout j faire trd(j)=t fin pour tout j;
pour tout i faire td(i)=-1 fin pour tout i;
pour tout j et tout v faire CUMUL(j,v)=0 fin pour tout j et pour tout v;
k=0;
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Placement des n tâches
tant que k < n faire
-----------------------------------------------------------
Placement des tâches sans prédécesseur qui n'utilisent aucune ressource
tant que il existe i sans prédécesseur et non placé qui n'utilise aucune ressource faire
td(i)=ASAP(i);
k=k+1 ;
fin tant que
-----------------------------------------------------------
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 alors FINmin=ASAP(i)+d(i) finsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'était 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)>PRIOmax alors
PRIOmax=PRIO(i);
imax = ifinsi ;
finsi toutes les tâches prédécesseur de i sont placées
finsi la tâche n'était pas encore placée
fin pour tout i
-----------------------------------------------------------
placement de la tâche imax
td(imax)=ASAP(imax);
pour j de 1 à r faire
pour v de ASAP(imax) à ASAP(imax)+d(imax)-1 faire
CUMUL(j,v)=CUMUL(j,v)+nrn(imax,j) ;
fin pour v;
fin pour j;
-----------------------------------------------------------
t=ASAPmin;
k=k+1;
finsi k < n
fin tant que
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Présentation de l'exercice qui suit
Dans l'exercice qui suit, on vous propose d'une part de simplifier les algorithmes précédents pour les faire passer du cas cumulatif avec un nombre quelconque de ressources au cas plus simple, disjonctif avec une seule ressource en un seul exemplaire.
Ensuite, on vous demande de les appliquer au problème de la paella.
