Sujet 3: Ordonnancement
Alan DAMOTTE, Romain BARTHELEMY
03/01/2015
Nous soussignés Barthelemy Romain et Damotte Alan déclarons sur l’honneur que ce rapport est le fruit d’un travail personnel, en binôme, que nous n’avons ni contrefait, ni falsifié, ni copié tout ou partie de l’œuvre d’autrui afin de la faire passer pour nôtre. Toutes les sources d’information utilisées et les citations d’auteur ont été mentionnées conformément aux usages en vigueur. Nous sommes conscient(e)s que le fait de ne pas citer une source ou de ne pas la citer clairement et complètement est constitutif de plagiat, que le plagiat est considéré comme une faute grave au sein de l’Université, pouvant être sévèrement sanctionnée par la loi.
Explications
Lorsque \(T=+\infty\), la condition Random < \(e^{\frac{-\Delta}{T}}\) est vérifiée quelque soit \(\Delta\) puisque \(e^{\frac{-\Delta}{T}}\rightarrow1\) et que \(Random < 1\). D’autre part, lorsque \(T=0\), cette condition n’est jamais vérifiée, puisqu’ici \(e^{\frac{-\Delta}{T}}\rightarrow0\) et que \(Random > 0\).
Dans chacun de ces cas, la condition de remplacement de C par C’ n’est pas significative.
La décroissance de \(T\) quant à elle doit se faire à la bonne vitesse. En effet, si \(T\) décroît “trop vite”, C ne sera pas optimisé efficacement puisqu’il n’y aura pas eu assez de tentatives pour trouver un bon résultat.
Si \(T\) décroît en revanche “trop lentement”, C sera trop souvent remplacé par C’ même lorsque cela n’est pas nécessaire, réalisant ainsi des tours de boucle inutiles. On aura au final un nombre de boucles bien trop grand et donc un temps d’exécution trop élevé.
Algorithme de génération
Voici la configuration initiale pour l’algorithme proposé par le sujet. Celle-ci se base sur des primitives fixes et d’autres pouvant être modifiées lors de la phase expérimentale, c’est le cas par exemple de actualize(T) qui peut être modifié afin d’analyser différents schémas de décroissance de température.
set.seed(42);
n=20;
M=5;
initial_value=10;
#Génère le tableau des tâches S1,...,Sn dont les éléments sont associés au temps mis par chaque tâche
generate_tasks <- function(){
S<-c();
for(i in 1:n){
S[i]=runif(1);
}
return(S);
}
S=generate_tasks();
#Alloue à chaque tâche Si une machine aléatoire entre 1 et M
generate_allocation <- function(){
x<-matrix(data=0,nrow=n,ncol=M);
for(i in 1:n){
x[i,ceiling(runif(1)*M)]=1;
}
return(x);
}
#Retourne le tableau où la tâche i est déplacée sur la machine j
move <- function (x,i,j){
x2<-x;
for(k in 1:M){
x2[i,k]=0;
}
x2[i,j]<-1;
return(x2);
}
#Renvoie le temps maximum des machines
MS <- function(x){
res<-0;
for(j in 1:M){
tmp<-0;
for(i in 1:n){
tmp<-tmp+x[i,j]*S[i];
}
if(tmp>res){
res<-tmp;
}
}
return(res);
}
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(initial_value-x);
}
#Temps d'allocation considéré comme bon
#On prend le temps MS réalisé par une répartition totalement équilibrée et on ajoute un epsilon
good_time <- function(){
tmp<-0;
min<-S[1];
for(i in 1:n){
tmp<-tmp+S[i];
if(S[i]<min){
min<-S[i];
}
}
#tmp/M correspond au temps parfait que MS(c) peut réaliser
#min est la valeur epsilon à rajouter de manière à ce que c puisse être accepté lorsque MS(c) est assez proche de la perfection
return(tmp/M + min)
}
#Algorithme de génération d'une répartition optimisée des tâches sur les machines disponibles
optimise <- function(){
c<-generate_allocation();
T<-initial_value;
cst<-good_time();
x<-1;
repeat{
i<-ceiling(runif(1)*n);
j<-ceiling(runif(1)*M);
c2<-move(c,i,j);
delta<-MS(c2)-MS(c);
if(runif(1)<exp(-delta/T)){
c<-c2;
}
T<-actualize(x);
x<-x+1;
#On vérifie que T n'a pas fini de décroître et que c n'a pas une assez bonne répartition des tâche
if(T<=0 || MS(c)<=cst){
break;
}
}
return(c);
}Ici, la loi répartissant la durée de chaque tâche est uniforme et permet une optimisation plus efficace. En effet, si il y a une valeur incroyablement plus grande que les autres, cela rend l’optimisation peu efficace puisque la machine s’occupant de la tâche en question prendra beaucoup de temps alors que les autres machines auront fini depuis longtemps.
Etude expérimentale
Initialisation
Dans cette partie, nous allons analyser plusieurs schémas de décroissance de température pour un nombre de tâches et de machines fixé. Nous gardons donc \(n=20\) et \(M=5\).
Les tests se feront sur une même instance de tâche et une même allocation initiale, ainsi, nous allons redéfinir certaines des primitives précédemment écrites afin de respecter ces contraintes.
S n’a pas à être modifié puisque l’algorithme proposé se fait à partir d’une répartition des tâches fixée, il ne reste donc plus qu’à faire en sorte que l’allocation initiale soit également fixée.
#On crée une répartition initiale des tâches entre les machines telle que cela a été défini précédemment
c_init<-generate_allocation();
#On redéfinit la fonction de génération d'allocation initiale de manière à ce que le résultat soit la répartition précédemment calculée
generate_allocation<-function(){
return(c_init);
}De cette manière, lorsque l’on fera appel à optimise(), la répartition initiale de c restera constante.
actualize() sera modifié au cours des différents tests, dépendant de la décroissance de température qui doit donc varier.
Les résultats du test se feront à l’aide de la fonction suivante:
etude_allocation<-function(k=100){
debut<-Sys.time();
MS<-c();
for(i in 1:k){
MS[i]<-MS(optimise());
}
hist(MS);
res=c();
#res[1]: moyenne des valeurs obtenues par optimise()
#res[2]: temps qu'on peut considérer comme bon
#res[3]: temps d'exécution du test en secondes
res[1]=mean(MS);
res[2]=good_time();
res[3]=(Sys.time()-debut)/k;
res;
}Les résultats renvoyés sont:
-L’histogramme de la répartition de MS(optimise()) pour les différents essais
-La moyenne des valeurs obtenues
-La valeur d’un MS considéré comme efficace
-Le temps d’exécution de la fonction
Tests de décroissance linéaire
Ici, nous allons réaliser les tests de décroissance linéaire de T. Tout d’abord, nous allons effectuer des tests avec initial_value=\(10\) et T suivant une fonction \(f(x)=-0.1x+10\) avec \(x\) associé au numéro du tour de boucle.
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(-0.1*x+initial_value);
}
etude_allocation();
## [1] 3.47731 2.57007 0.03042Lors de ce test, nous pouvons voir que peu de résultats se rapprochent d’une allocation efficace, c’est-à-dire vers la valeur renvoyée par good_time(). Nous avons même une grosse quantité de valeurs très éloignées de good_time(), nous sommes donc dans ces cas-là face à un manque d’efficacité.
La raison peut venir du fait que la décroissance de T est trop rapide et empêche d’avoir un résultat parfaitement optimisé. Essayons donc cette fois-ci avec une fonction de décroissance de température moins abrupte: \(f(x)=-0.005x+10\)
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(-0.005*x+initial_value);
}
etude_allocation();
## [1] 2.7885 2.5701 0.5189Nous avons ici des valeurs de \(MS(optimise())\) bien plus proches d’une bonne optimisation. Cependant, cela a eu pour conséquence d’avoir un temps d’exécution par appel à optimise() près de 20 fois plus important qu’avant (ce qui semble logique vu la décroissance de T 20 fois plus lente).
Voyons si il n’y a pas moyen d’obtenir des résultats tout aussi efficaces pour un temps d’exécution plus petit.
Test de décroissance sous forme quadratique
Cette fois-ci, l’évolution de T se fera sous la forme d’une courbe non linéaire, avec T suivant une fonction \(f(x)=-0.635*x+10+0.01*x^2\) valant 0 à une certaine valeur entière permettant ainsi au programme de terminer.
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(-0.635*x+initial_value+0.01*x^2);
}
etude_allocation();
## [1] 3.55741 2.57007 0.00833De la même manière que le premier test, nous avons une optimisation peu efficace, cependant on peut noter que la vitesse d’exécution est nettement plus rapide.
Faisons à présent le test pour une courbe du même genre décroissant plus lentement, avec \(f(x)=-0.0635*x+10+0.0001*x^2\).
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(-0.0635*x+initial_value+0.0001*x^2);
}
etude_allocation();
## [1] 2.88759 2.57007 0.08054Nous tombons sur des résultats du même type que ceux du second test linéaire, mais de manière bien plus rapide.
Cela s’explique par le fait que les valeurs les plus intéressantes se trouvent lorsque T est proche de 0. En effet, à ce stade là, le remplacement de C se fera sous des contraintes plus strictes, permettant d’obtenir un C tendant plus efficacement vers sa valeur optimale.
Ici, la décroissance de T se fait de manière à ce que la majorité des occurences de la boucle principale se font lorsque T est proche de 0, ce qui cause donc les résultats obtenus.
Test de la valeur initiale de T
Nous avons pu deviner que les valeurs proches de 0 sont celles permettant d’accéder plus rapidement à un résultat satisfaisant. Afin de confirmer cette théorie, nous allons revenir sur le modèle linéaire. Nous allons réaliser 2 tests différents, avec un nombre de tours de boucle équivalent. Le premier aura une valeur initiale élevée et décroîtra plus rapidement, tandis que le second montrera ce qui se passe dans le cas contraire.
initial_value<-100;
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(-0.1*x+initial_value);
}
etude_allocation();
## [1] 3.4210 2.5701 0.2738Les résultats obtenus sont peu concluants, nos valeurs sont rarement proches d’un MS optimisé. A présent voyons la configuration opposée.
initial_value<-1;
#Fonction déterminant le schéma de décroissance de température
actualize <- function(x){
return(-0.001*x+initial_value);
}
etude_allocation();
## [1] 2.6560 2.5701 0.2532Nous avons approximativement la même durée d’exécution, cependant nous sommes incroyablement plus proches d’une optimisation optimale, comme nous l’avions prévu.
Ainsi, si nous souhaitons réaliser une optimisation efficace à moindre coûts, mieux vaut décroître plus lentement avec une température initiale faible.