Algo

branch and bound algo d'ordonencement de taches

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : branch and bound algo d'ordonencement de taches

maniweb

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 :

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

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

Code :

package scheduling;
public class Problem {
// array containing jobs to do
// jobTable[0] = 1 means that the first job is a "task 1"
private short[] jobTable;
// array contening machin names
private String[] machinNameTable;
// array contening the time taken by each task for each machins
// timeTable[0][3] = 10 means that the "task 3" take 10u for machin 0
private short[][] timeTable;
// array contening the solution found
// solutionTable[3] give the machins who will do the job nb 3
private short[] solutionTable;
// minmimum time found to resolve de problem
private short bestTime = (short) 10000;
// number of node explored
private long count = 0;
/**
* Constructor of the class, set the properties
*
* @param quantityTable
* @param nameTable
* @param timeTable
*/
public Problem(short[] jobTable, String[] machinNameTable,
short[][] timeTable) {
// set properties
this.jobTable = jobTable;
this.machinNameTable = machinNameTable;
this.timeTable = timeTable;
// init solutionTable
solutionTable = new short[jobTable.length];
}
/**
* start a new tree, in fact start creating as sub tree as machins
*
*/
public void solve() {
System.out.println("***** Calcul started *****" );
for (short i = 0; i < machinNameTable.length; ++i)
buildTree(i, (short) 0, new short[jobTable.length],
(short[]) solutionTable.clone());
System.out.println("***** Calcul finished *****" );
writeResult("result.txt" );
}
/**
* build the tree recursively
*
* @param machinNumber
* the machin were the current job is going to be executed
* @param jobNumber
* the number of the current Job
* @param machinsTime
* an array containing the elapsed time for each computer
*
*
*/
public void buildTree(short machinNumber, short jobNumber,
short[] machinsTime, short[] tmpSolutionTable) {
// increase the executing time of the concerned machin
short increase = timeTable[machinNumber][jobTable[jobNumber]];
if (increase == Short.MAX_VALUE) // the machin can't do this task
return;
// increase the number of nodes visited
count++;
// increase the time of the concerned machin
machinsTime[machinNumber] += increase;
// calculate the global time ie the max of all the machin's time
short elapsedTime = machinsTime[0];
for (short i = 1; i < machinsTime.length; ++i)
elapsedTime = (elapsedTime > machinsTime[i]) ? elapsedTime
: machinsTime[i];
if (jobNumber + 1 == jobTable.length) { // we are executing the last job
if (elapsedTime < bestTime) {
// set the new best time
bestTime = elapsedTime;
// update the solutionTable
solutionTable = tmpSolutionTable;
solutionTable[jobNumber] = machinNumber;
System.out.println("new best time : " + bestTime);
}
} else if (elapsedTime < bestTime) { // continue the tree exploration
// update the solutionTable
tmpSolutionTable[jobNumber] = machinNumber;
// avoid redundant cases
short startIndex = 0;
if (jobTable[jobNumber] == jobTable[jobNumber + 1])
startIndex = machinNumber;
for (short newMachinNumber = startIndex; newMachinNumber < machinNameTable.length; ++newMachinNumber)
buildTree(newMachinNumber, (short) (jobNumber + 1),
(short[]) machinsTime.clone(),
(short[]) tmpSolutionTable.clone());
}
}
/**
* @return Returns the solutionTable.
*/
public short[] getSolutionTable() {
return solutionTable;
}
}

Publicité

Kyle_Katarn

pourquoi tu ne fais pas un PERT ?

maniweb

kasako ?

maniweb

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 ...

lbasic

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

Ace17

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

Message cité 1 fois

maniweb

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

lbasic

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

maniweb

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 :

the total elapsed time is : 254
**********************************************
Machine A has executed :
5 task n°1 - 60
0 task n°2 - 0
1 task n°3 - 14
0 task n°4 - 0
5 task n°5 - 80
4 task n°6 - 60
2 task n°7 - 40
total : 254
**********************************************
Machine B has executed :
0 task n°1 - 0
5 task n°2 - 125
3 task n°3 - 51
3 task n°4 - 78
0 task n°5 - 0
0 task n°6 - 0
0 task n°7 - 0
total : 254
**********************************************
Machine C has executed :
0 task n°1 - 0
0 task n°2 - 0
1 task n°3 - 23
2 task n°4 - 84
0 task n°5 - 0
1 task n°6 - 32
3 task n°7 - 114
total : 253
**********************************************

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

lbasic

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

Publicité

maniweb

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 !

maniweb

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

maniweb

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
**********************************************

lbasic

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

lbasic

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

maniweb

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

Dodge_Kowalski

Chased by the blue

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 :??:

rufo

Pas me confondre avec Lycos!

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

jeoff

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.

trevor

laissez la vie vous étonner...

drapeau

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

jimipage

déclarer c'est fatiguant

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

lkolrn

Ace17 a écrit :

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

ui plutôt ui

jimipage

déclarer c'est fatiguant

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

jimipage

déclarer c'est fatiguant

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

jimipage

déclarer c'est fatiguant

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

lkolrn

t1 les gars, algo du simplexe.. [:arod]

Si ça peut vous encourager : vous en êtes au début... :whistle:

jimipage

déclarer c'est fatiguant

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

rufo

Pas me confondre avec Lycos!

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

jimipage

déclarer c'est fatiguant

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]

jeoff

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

Publicité

FORUM HardWare.fr

Programmation

Algo

branch and bound algo d'ordonencement de taches

Sujets relatifs
Algo pour effectuer une intégrale	Donnez moi l'Algo de génération / Récup des PAR2...
Je cherche un exemple d'algo type arbre shv	Aide pour faire un puissance 4 (algo qui recherche les solution).
algo inversement de bits	Liens vers problèmes d'algo
Juste pour avoir une informayion sur cet algo	icone dans la barre des taches
Algo Conversion Notation Infixe en Notation Polonaise Inverse	Algo avec Alg_exec ( Algo de base, mais qui pose probleme...)
Plus de sujets relatifs à : branch and bound algo d'ordonencement de taches

Page générée en 0.135 secondes