branch and bound algo d'ordonencement de taches

branch and bound algo d'ordonencement de taches - Algo - Programmation

Marsh Posté le 08-12-2005 à 12:44:03    

Bonjour, a tous
 
J'ai un probleme d'ordonencement de tache à réaliser dont voici le sujet :
 
 
                 Tâche1  Tâche2   Tâche3   Tâche4   Tâche5   Tâche6  Tâche7  
 
Machine A       12         23         14         NO         16         15         20  
Machine B       34         25         17         26          29         30         NO  
Machine C       37         NO         23         42         NO         32         38  
******************************************************      TOTAL
Quantité         34         56         39         71         18         45         34         297
 
 
Le but du problème est d'effectuer en minimum de temps les 297 tâches. Sachant que chaque machine ne peut réaliser qu'une seule tache à la fois (mais qu'on peut bien sur utiliser les 3 machines en même temps). Le tableau indique pour chaque machine combien d'unité de temps coûte chaque tâche. Une case contenant No signifie que la machine ne peut pas effectuer cette tache. On peut effectuer les tâches dans l'ordre qu'on veut.
 
Je doit trouver la solution en utilisant un arbre, on m'a orienté vers l'algorithme branch and bound
mais pour l'instant l'algorithme que j'ai réalisé ne se finit pas car meme en coupant beaucoup de branches
il reste toujours beaucoup trop de solutions a calculer
 
voila un aperçu de ce que j'ai déja fait (en java )
 
en gros je construit l'arbre en profondeur de façon récursif en évitant les permutations inutiles et en coupant lorsque le temps calculé dépasse le temps minimum trouvé jusqu a la.
 
Si vous avez une idée a me donner elle sera la bien venue  
 
A bientot maniweb
 
fichier contenant le main

Code :
  1. package main;
  3. import scheduling.Problem;
  5. public class Run {
  7. /**
  8.  * @param args
  9.  */
  10. public static void main(String[] args) {
  12.  // list of the machins
  13.  String[] machinNameTable = { "Machine A", "Machine B", "Machine C" };
  15.  // time for each task for each machin
  16.  short[][] timeTable = { { 12, 23, 14, Short.MAX_VALUE, 16, 15, 20 },
  17.    { 34, 25, 17, 26, 29, 30, Short.MAX_VALUE },
  18.    { 37, Short.MAX_VALUE, 23, 42, Short.MAX_VALUE, 32, 38 } };
  20.  // quantity for each task
  21.  short[] quantity = { 34, 56, 39, 71, 18, 45, 34 };
  23.  // calculate the total number of jobs
  24.  short size = 0;
  25.  for (short i = 0; i < quantity.length; i++)
  26.   size += quantity[i];
  28.  // build the list of all the jobs
  29.  short[] jobTable = new short[size];
  31.  short i = 0, k = 0;
  33.  while (i < jobTable.length) {
  35.   for (short j = 0; j < quantity[k]; j++)
  36.    jobTable[i + j] = k;
  37.   i += quantity[k];
  39.   k++;
  40.  }
  42.  Problem pb = new Problem(jobTable, machinNameTable, timeTable);
  44.  pb.solve();
  45. }
  46. }


 
fichier conteant la classe appelé par le main qui construit l arbre de faco

Code :
  1. package scheduling;
  3. public class Problem {
  5. // array containing jobs to do
  6. // jobTable[0] = 1 means that the first job is a "task 1"
  7. private short[] jobTable;
  9. // array contening machin names
  10. private String[] machinNameTable;
  12. // array contening the time taken by each task for each machins
  13. // timeTable[0][3] = 10 means that the "task 3" take 10u for machin 0
  14. private short[][] timeTable;
  16. // array contening the solution found
  17. // solutionTable[3] give the machins who will do the job nb 3
  18. private short[] solutionTable;
  20. // minmimum time found to resolve de problem
  21. private short bestTime = (short) 10000;
  23. // number of node explored
  24. private long count = 0;
  26. /**
  27.  * Constructor of the class, set the properties
  28.  *  
  29.  * @param quantityTable
  30.  * @param nameTable
  31.  * @param timeTable
  32.  */
  33. public Problem(short[] jobTable, String[] machinNameTable,
  34.   short[][] timeTable) {
  36.  // set properties
  37.  this.jobTable = jobTable;
  38.  this.machinNameTable = machinNameTable;
  39.  this.timeTable = timeTable;
  41.  // init solutionTable
  42.  solutionTable = new short[jobTable.length];
  43. }
  45. /**
  46.  * start a new tree, in fact start creating as sub tree as machins
  47.  *  
  48.  */
  49. public void solve() {
  51.  System.out.println("***** Calcul started *****" );
  53.  for (short i = 0; i < machinNameTable.length; ++i)
  54.   buildTree(i, (short) 0, new short[jobTable.length],
  55.     (short[]) solutionTable.clone());
  57.  System.out.println("***** Calcul finished *****" );
  59.  writeResult("result.txt" );
  60. }
  62. /**
  63.  * build the tree recursively
  64.  *  
  65.  * @param machinNumber
  66.  *            the machin were the current job is going to be executed
  67.  * @param jobNumber
  68.  *            the number of the current Job
  69.  * @param machinsTime
  70.  *            an array containing the elapsed time for each computer
  71.  *  
  72.  *  
  73.  */
  74. public void buildTree(short machinNumber, short jobNumber,
  75.   short[] machinsTime, short[] tmpSolutionTable) {
  77.  // increase the executing time of the concerned machin
  78.  short increase = timeTable[machinNumber][jobTable[jobNumber]];
  79.  if (increase == Short.MAX_VALUE) // the machin can't do this task
  80.   return;
  82.  // increase the number of nodes visited
  83.  count++;
  85.  // increase the time of the concerned machin
  86.  machinsTime[machinNumber] += increase;
  88.  // calculate the global time ie the max of all the machin's time
  89.  short elapsedTime = machinsTime[0];
  90.  for (short i = 1; i < machinsTime.length; ++i)
  91.   elapsedTime = (elapsedTime > machinsTime[i]) ? elapsedTime
  92.     : machinsTime[i];
  94.  if (jobNumber + 1 == jobTable.length) { // we are executing the last job
  96.   if (elapsedTime < bestTime) {
  97.    // set the new best time
  98.    bestTime = elapsedTime;
  100.    // update the solutionTable
  101.    solutionTable = tmpSolutionTable;
  102.    solutionTable[jobNumber] = machinNumber;
  104.    System.out.println("new best time : " + bestTime);
  105.   }
  107.  } else if (elapsedTime < bestTime) { // continue the tree exploration
  109.   // update the solutionTable
  110.   tmpSolutionTable[jobNumber] = machinNumber;
  112.   // avoid redundant cases
  113.   short startIndex = 0;
  114.   if (jobTable[jobNumber] == jobTable[jobNumber + 1])
  115.    startIndex = machinNumber;
  117.   for (short newMachinNumber = startIndex; newMachinNumber < machinNameTable.length; ++newMachinNumber)
  118.    buildTree(newMachinNumber, (short) (jobNumber + 1),
  119.      (short[]) machinsTime.clone(),
  120.      (short[]) tmpSolutionTable.clone());
  121.  }
  122. }
  124. /**
  125.  * @return Returns the solutionTable.
  126.  */
  127. public short[] getSolutionTable() {
  128.  return solutionTable;
  129. }
  130. }

       
         
         
       
       

Reply

Marsh Posté le 08-12-2005 à 12:44:03   

Reply

Marsh Posté le 08-12-2005 à 12:44:55    

pourquoi tu ne fais pas un PERT ?

Reply

Marsh Posté le 08-12-2005 à 13:10:51    

kasako ?

Reply

Marsh Posté le 08-12-2005 à 13:33:21    

Je ne sais pas trop si il faut que j applique PERT mais dans mon probleme les taches n'ont aucun lien de dépendance on peut faire executer la tache 7 et la tache 1 par deux machines etc ...

Reply

Marsh Posté le 09-12-2005 à 01:39:33    

j'ai eu un peu de mal mais j'ai fait un prog qui me donne ça comme solution :
 
sur la machine A
les taches 1,2, et 7
 
sur la machine B
les taches 4 et 5
 
sur la machine C
les taches 3 et 6
 
Avec 55 en unité de temps sur chaque machine.
c'est bien ça que tu cherche à faire ?
 
@++


---------------
Liberty BASIC France : http://www.lbasic.fr
Reply

Marsh Posté le 09-12-2005 à 08:33:46    

C'est plutot de l'algorithme du simplexe que tu aurais besoin, non?

Message cité 1 fois
Reply

Marsh Posté le 09-12-2005 à 19:04:08    

Hello excusez moi du retard
 
Ibasic en faite il faut faire faire en tout 297 taches au 3 machines, la quantité pour chaque tache est indiqué dans la derniere colonne
pour ma part j ai trouvé un temps de 2322 je croix mais comme mon algo ne se finit pas il se peut qu il existe des temps mieux que ca
 
pour simplexe j ai regardé en vitesse mais je pense pas que ca soit ca
 
mervi de votre aide je vous tiens au courant  
 
A+


Message édité par maniweb le 09-12-2005 à 19:11:59
Reply

Marsh Posté le 09-12-2005 à 20:52:55    

Dsl, j'avais pas compris ça !
pour verifier : Je reformule.
la tache 1 doit utiliser 12 UT sur la machine A, 34 UT sur la B et 37 UT sur la C.
a quoi correspond le 34 ? en haut tu ecris "tache 1" et il semble que 34 corresponde aux nbre de taches necessaire pour effectuer les operations sur les 3 Machines. Donc la "tache 1" correspond en fait à 34 taches (plus petites), c'est ça ?


---------------
Liberty BASIC France : http://www.lbasic.fr
Reply

Marsh Posté le 10-12-2005 à 13:23:16    

34 c'est le nombre de fois que doit etre executer la tache numero 1.  
tu peux repartir les 34 taches entre les 3 machines comme tu veux leur ut respectifs sont bien comme tu dit 12 34 et 37
 
En gros il faut effectuer 297 "taches" dont la repartition est decrite dans la ligne quantité
 
je te montre un exemple j'ai testé mon programme avec le meme tableau que ci dessus mais avec moins de taches a executer pour que mon prgm puisse finir voila le resultat que j obtiens
 
mon probleme c est que mon algo n'est pas assez performant pour le nombre de taches indiqué dans le premier tableau
 
 
le tableau est le meme seule la derniere colonne change
 
                 Tâche1  Tâche2   Tâche3   Tâche4   Tâche5   Tâche6  Tâche7  
 
Machine A       12         23         14         NO         16         15         20  
Machine B       34         25         17         26          29         30         NO  
Machine C       37         NO         23         42         NO         32         38  
******************************************************      TOTAL
Quantité         5           5           5          5            5           5          5         35
 

Code :
  1. the total elapsed time is : 254
  3. **********************************************
  4. Machine A has executed :
  5.  5 task n°1 - 60
  6.  0 task n°2 - 0
  7.  1 task n°3 - 14
  8.  0 task n°4 - 0
  9.  5 task n°5 - 80
  10.  4 task n°6 - 60
  11.  2 task n°7 - 40
  12. total : 254
  13. **********************************************
  14. Machine B has executed :
  15.  0 task n°1 - 0
  16.  5 task n°2 - 125
  17.  3 task n°3 - 51
  18.  3 task n°4 - 78
  19.  0 task n°5 - 0
  20.  0 task n°6 - 0
  21.  0 task n°7 - 0
  22. total : 254
  23. **********************************************
  24. Machine C has executed :
  25.  0 task n°1 - 0
  26.  0 task n°2 - 0
  27.  1 task n°3 - 23
  28.  2 task n°4 - 84
  29.  0 task n°5 - 0
  30.  1 task n°6 - 32
  31.  3 task n°7 - 114
  32. total : 253
  33. **********************************************


 
j'espere que c'est plus clair, c est super sympa de passer autant de temps a m aider en tout cas  
 
A+ PG


Message édité par maniweb le 10-12-2005 à 13:28:57
Reply

Marsh Posté le 10-12-2005 à 17:43:52    

Je commence à comprendre.
si on regarde les arrangements possibles de chaque tache sur chaque machine, on arrive à environ 5.07*10^9 possibilités, c'est enorme !
on peu envisager une autre solution qui consiste à regarder les arrangements de 7 taches differentes. on arrive à un resultat de 55 unités de temps sur chaque machine. (c'est la solution que j'avais trouvé precedement).
 
ensuite on regarde le nombre de fois que l'on peu reproduire cet arrangement (c'est le nombre le plus petits de la repetition des taches) c'est à dire 18 fois.
 
je reformule : en faisant 18 fois l'arrangement AACBBCA à 7 taches j'obtiens un temps total de 18*55=990 UT pour un total de 126 taches.
 
la tache numero 5 est maintenant terminée en totalité. il me reste donc 6 taches à effectuées. Je recommence mon calcul et ainsi de suite avec ces nouvelles données.
 
(j'ai enlevé 18 partout)
 
              Tâche1  Tâche2   Tâche3   Tâche4   Tâche5   Tâche6  Tâche7  
 
Machine A       12         23         14         NO         16         15         20  
Machine B       34         25         17         26          29         30         NO  
Machine C       37         NO         23         42         NO         32         38  
******************************************************      TOTAL
Quantité        16         38         39         21         0         27         16         171  
 
j'essaye de coder ça....
 
@++


---------------
Liberty BASIC France : http://www.lbasic.fr
Reply

Marsh Posté le 10-12-2005 à 17:43:52   

Reply

Marsh Posté le 11-12-2005 à 03:16:34    

hello
 je suis pas sur que ce soit le bon resonnement, en effet tu risque de te retrouver avec des machines qui ne peuvent plus faire de tache par exemple si il ne te reste plus que les taches 2 et 5 la machine C ne sert plus a rien,  
Je pense qu on est obligé de passer par un arbre pour trouver  la solution minimale, il y a surement une methode pour couper suffisement de branches pour parvenir a finir le parcour de l'arbre
 
quel casse tête !

Reply

Marsh Posté le 11-12-2005 à 03:22:20    

j ai essayé mon algorithme en mettant que des 18 j arrive a des temps inferieur a 990

Reply

Marsh Posté le 11-12-2005 à 11:01:31    

voila un exemple de solution < 990
 
**********************************************
Machine A has executed :
  18 task n°1 - 216
  18 task n°2 - 414
  7 task n°3 - 98
  0 task n°4 - 0
  7 task n°5 - 112
  9 task n°6 - 135
  0 task n°7 - 0
total : 975
**********************************************
Machine B has executed :
  0 task n°1 - 0
  0 task n°2 - 0
  11 task n°3 - 187
  18 task n°4 - 468
  11 task n°5 - 319
  0 task n°6 - 0
  0 task n°7 - 0
total : 974
**********************************************
Machine C has executed :
  0 task n°1 - 0
  0 task n°2 - 0
  0 task n°3 - 0
  0 task n°4 - 0
  0 task n°5 - 0
  9 task n°6 - 288
  18 task n°7 - 684
total : 972
**********************************************

Reply

Marsh Posté le 11-12-2005 à 11:29:30    

avec le mien pour ton pb et avant optimisation, je suis dans les 2400 ut (pour tout faire).
je continue à chercher. Je serais absent cet AM.
 
va quand même falloir que je revois mon algo !
 
@++


Message édité par lbasic le 11-12-2005 à 11:48:24

---------------
Liberty BASIC France : http://www.lbasic.fr
Reply

Marsh Posté le 12-12-2005 à 00:02:04    

Bon,
j'ai codé un prog qui fonctionne par recurence et qui teste toutes les possibilités.
mais en BASIC, et là AU SECOURS.....
ça fait 3 heures qu'il tourne !
faut que je ressorte mes bouqins de C++, sinon dans 1 an j'aurais fait que trois tests.
 
je me mets à chercher pour eliminer des branches plus rapidement....
la seule piste que j'ai pour l'instant est un calcul probabiliste....
 
work and see  :-))
 
@++


---------------
Liberty BASIC France : http://www.lbasic.fr
Reply

Marsh Posté le 12-12-2005 à 01:57:19    

moi apres une nuit j'etais dans les 2322 il me semble ...
 
le truc c est que meme en supprimant des branches l'arbre a une profondeur de 297 max meme si on arrivait a en couper la moitié a chaqe fois ily en aurait tjrs trop
 
je continue de chercher
A+


Message édité par maniweb le 12-12-2005 à 01:59:29
Reply

Marsh Posté le 20-01-2006 à 00:52:33    

un petit [:undertaker666]
 
Vous avez trouver une méthode intéressante?
Comme meilleur solution vous êtes arrivé à quoi?
 
C'est énervant ce truc, ça à l'air tout con, mais sans rien programmer pour l'instant, j'arrive pas à descendre en dessous de 2546. Il doit bien y avoir une approche logique  :??:

Reply

Marsh Posté le 20-01-2006 à 09:17:05    

t'as regardé un peu dans la littérature de l'ordo? Y'aurait que 2 machines, ton pb était résolu par l'algo de Johnson. Quand on l'avait étudié à l'école, notre prof nous avait montré qu'on pouvait modifier les données initiales d'un pb afin de le ramener dans les conditions d'utilisation de Johnson. Donc regarde si ton pb peut être ramené à Johnson...
 
Sinon, pour réduire la combinatoire, tu peux chercher du côté des algo génétiques. Tu générès une population d'individus aléatoirement où chaque individu représente une solution (un ordonnanement possible) à ton pb. Tu effectues des croisements entre certains individus afin de générer la nouvelle population. Pour chaque population, tu regardes le meilleur individu (ici, celui qui a le Cmax le plus petit) et tu le compares au meilleur individu de la génération précédente. Tu génères un certain nb de populations et à la fin, tu devrais avoir une bonne solution, voire, si tu y rajoutes un peu d'intélligence et que tu fais suffisamment d'itérations, avoir la meilleure solution.

Message cité 1 fois
Reply

Marsh Posté le 20-01-2006 à 10:09:50    

Quelques liens pioché sur google
 
ftp://ftp.inria.fr/INRIA/publicat [...] R-2505.pdf
 
http://biblion.epfl.ch/EPFL/theses [...] 64_abs.pdf
 
http://www.cs.ualberta.ca/~sutton/ [...] de113.html
 
Concernant Johnson, il me semble valide uniquement si les tâches se voient un ordre de passage imposé (machine1 puis 2 puis 3).
Par contre il est tout a fait possible de s'en servir pour calculer une solution initiale et l'améliorer par la suite en permuttant l'ordre des machines.
 
De mes lointains souvenirs d'ordonnancement, tu devrais tester google avec lagrangien, heuristique (++), meta heuristique (++), np complet.
 
Même si on sait résoudre ce genre de problèmes de manière déterministe, la population de solutions croit tellement vite que tu devras certainement te contenter d'un algo pour approcher la meilleure solution et non l'atteindre à coup sûr.

Reply

Marsh Posté le 20-01-2006 à 10:37:10    

drapeau


---------------
TReVoR - http://dev.arqendra.net - http://info.arqendra.net
Reply

Marsh Posté le 21-01-2006 à 02:55:14    

avec ça j'ai 2407, mais j'ai n'ai rien fait dans mon programme pour voir à long terme
il faudrait peut-être que je résonne avec des échanges de plusieurs tâches en même temps,
et, comme il a été dit plus haut, avec des arbres...
ce qui est pratique, c'est que le programme met moins d'une seconde
ce qui l'est moins, c'est que la solution est peut-être très éloignées en terme de distribution des tâches :sweat:
 
machine 1 job 1 : 34
machine 1 job 2 : 56
machine 1 job 3 : 0
machine 1 job 4 :
machine 1 job 5 : 0
machine 1 job 6 : 2
machine 1 job 7 : 34
 
temps total pour cette machine : 2406
 
machine 2 job 1 :
machine 2 job 2 :
machine 2 job 3 : 39
machine 2 job 4 : 47
machine 2 job 5 : 18
machine 2 job 6 :
machine 2 job 7 :
 
temps total pour cette machine : 2407
 
machine 3 job 1 :
machine 3 job 2 :
machine 3 job 3 :
machine 3 job 4 : 24
machine 3 job 5 :
machine 3 job 6 : 43
machine 3 job 7 :
 
temps total pour cette machine : 2384


Message édité par jimipage le 21-01-2006 à 12:44:07
Reply

Marsh Posté le 21-01-2006 à 03:24:53    

Ace17 a écrit :

C'est plutot de l'algorithme du simplexe que tu aurais besoin, non?


ui plutôt ui ;)

Reply

Marsh Posté le 21-01-2006 à 12:39:12    

pour un programme qui tourne 5 secondes, 2290 c'est déjà moins mauvais :
 
machine 1 job 1 : 17
machine 1 job 2 : 40
machine 1 job 3 : 0
machine 1 job 4 : 0
machine 1 job 5 : 13
machine 1 job 6 : 33
machine 1 job 7 : 29
 
temps total pour cette machine : 2290
 
machine 2 job 1 : 7
machine 2 job 2 : 16
machine 2 job 3 : 31
machine 2 job 4 : 40
machine 2 job 5 : 5
machine 2 job 6 : 1
machine 2 job 7 : 0
 
temps total pour cette machine : 2288
 
machine 3 job 1 : 10
machine 3 job 2 : 0
machine 3 job 3 : 8
machine 3 job 4 : 31
machine 3 job 5 : 0
machine 3 job 6 : 11
machine 3 job 7 : 5
 
temps total pour cette machine : 2267

Reply

Marsh Posté le 21-01-2006 à 12:47:41    

si je le fais tourner 1 minute, il trouve 2276, ça doit commencer à converger... et comme c'est une adaption libre de monte-carlo, on finit par balayer un poeu tout
 
machine 1 job 1 : 6
machine 1 job 2 : 45
machine 1 job 3 : 15
machine 1 job 4 : 0
machine 1 job 5 : 18
machine 1 job 6 : 34
machine 1 job 7 : 14
 
temps total pour cette machine : 2269
 
machine 2 job 1 : 7
machine 2 job 2 : 11
machine 2 job 3 : 7
machine 2 job 4 : 68
machine 2 job 5 : 0
machine 2 job 6 : 0
machine 2 job 7 : 0
 
temps total pour cette machine : 2276
 
machine 3 job 1 : 21
machine 3 job 2 : 0
machine 3 job 3 : 17
machine 3 job 4 : 3
machine 3 job 5 : 0
machine 3 job 6 : 11
machine 3 job 7 : 20
 
temps total pour cette machine : 2259

Reply

Marsh Posté le 21-01-2006 à 13:55:54    

rufo a écrit :


Tu effectues des croisements entre certains individus afin de générer la nouvelle population. Pour chaque population, tu regardes le meilleur individu (ici, celui qui a le Cmax le plus petit) et tu le compares au meilleur individu de la génération précédente..


 
C'est en gros ce que j'avais fait au début (mais la population initiale n'était pas aléatoire), en regardant ce qui était le moins coûteux pour les échanges
les tests sont les suivants :
-> je regarde la machine qui tourne le plus longtemps
-> je regarde ce qui est le moins coûteux comme échange de tâche
-> j'arrête quand j'ai atteint le minimum, qui est hélas un minimum local
 
Le problème, c'est que pour des temps très proches, on peut avoir des répartitions très différentes
pour tomber sur un autre minimum, il faut partir d'une autre population initiale
 
 

rufo a écrit :


Tu génères un certain nb de populations et à la fin, tu devrais avoir une bonne solution, voire, si tu y rajoutes un peu d'intélligence et que tu fais suffisamment d'itérations, avoir la meilleure solution.


 
effectivement, je génère des populations initiales aléatoirement, et je tombe sur différents minima locaux.
un jour ou l'autre, on devrait bien trouver le minimum global... :wahoo:
 
un dernier pour la route à 2268, et je vais bosser :
 
machine 1 job 1 : 33
machine 1 job 2 : 12
machine 1 job 3 : 22
machine 1 job 4 : 0
machine 1 job 5 : 18
machine 1 job 6 : 38
machine 1 job 7 : 21
 
temps total pour cette machine : 2258
 
machine 2 job 1 : 0
machine 2 job 2 : 44
machine 2 job 3 : 6
machine 2 job 4 : 41
machine 2 job 5 : 0
machine 2 job 6 : 0
machine 2 job 7 : 0
 
temps total pour cette machine : 2268
 
machine 3 job 1 : 1
machine 3 job 2 : 0
machine 3 job 3 : 11
machine 3 job 4 : 30
machine 3 job 5 : 0
machine 3 job 6 : 7
machine 3 job 7 : 13
 
temps total pour cette machine : 2268

Reply

Marsh Posté le 21-01-2006 à 14:36:56    

t1 les gars, algo du simplexe.. [:arod]
 
Si ça peut vous encourager : vous en êtes au début... :whistle:

Reply

Marsh Posté le 21-01-2006 à 18:10:18    

oulala j'étais loin d'avoir optimiser mon programme !!!
je ne sais pas ce que donne simplex, mais monte-carlo descend à 2233 !!!
bon ok, j'ai utilisé mes premiers résultats pour repérer les ressemblances entre les configurations obtenues, me permettant de pondérer les probabilités des conditions initiales.
Il fallait donc bien commencer par des résultats moyens...
 
machine 1 job 1 : 34
machine 1 job 2 : 6
machine 1 job 3 : 3
machine 1 job 4 : 0
machine 1 job 5 : 18
machine 1 job 6 : 45
machine 1 job 7 : 34
 
temps total pour cette machine : 2231
 
machine 2 job 1 : 0
machine 2 job 2 : 50
machine 2 job 3 : 1
machine 2 job 4 : 37
machine 2 job 5 : 0
machine 2 job 6 : 0
machine 2 job 7 : 0
 
temps total pour cette machine : 2229
 
machine 3 job 1 : 0
machine 3 job 2 : 0
machine 3 job 3 : 35
machine 3 job 4 : 34
machine 3 job 5 : 0
machine 3 job 6 : 0
machine 3 job 7 : 0
 
temps total pour cette machine : 2233
 
le programme donne ce résultat en 1 seconde, toujours le même...
mais avec les pondérations sur les conditions initiales, on ne balaye plus tout l'espace
il ne faut donc pas qu'un meilleur minimum se trouve caché qqpart...
 
je pense bien avoir trouvé le minimum... qui dit mieux ? ?? :hello:
 
Nouveaux tests repartant du début : j'en suis même presque sûr !


Message édité par jimipage le 21-01-2006 à 18:49:53
Reply

Marsh Posté le 26-01-2006 à 18:27:43    

pour améliorer, tu peux regarder du côté de l'algo du recuit. En +, j'avais lu qq part qu'il y avait des méthodes pour sortir d'un minimum local...

Message cité 1 fois
Reply

Marsh Posté le 26-01-2006 à 20:20:29    

rufo a écrit :

pour améliorer, tu peux regarder du côté de l'algo du recuit. En +, j'avais lu qq part qu'il y avait des méthodes pour sortir d'un minimum local...


 
En effet, je crois qu'il y a énormément de choses à prendre du côté des processus stochastiques...
surtout lorsque ça peut nous éviter de faire tourner des programmes pendant des jours pour trouver un semblant de début de résultat
 
je crois que je ne vais pas tarder à tester ce recuit sur quelques problèmes de minimisations de fonctions... [:ewil2001]

Reply

Marsh Posté le 27-01-2006 à 10:19:40    

le recuit marche bien, jette un oeil sur le kangourou (sisi c'est pas une blague:D) également pour t'extraire des minima locaux

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed