idée d'algorithme d'affectation

Version imprimable

21/08/2009, 16h11
laureat

idée d'algorithme d'affectation

En fait, le problème consiste à placer n taches sur m machines pour minimiser les retards totaux.
La règle est la suivante : placer la tache dont la durée d'exécution est la plus petite à la machine disponible.
A chaque fois on doit calculer le retard "T" de chaque tache (formule est la suivante : date de fin d'exécution de la tache "c" -date de fin au plus tard de la tache "d") : T= c -d.
Ce qui est demandé :
1) écrire un programme qui permet de trier les taches par durée d'exécution croissant: c'est fait!

2) écrire un programme qui permet placer les taches sur les machines pour calculer les retards totaux selon la formule donnée.
Là, je me bloque . Je n'arrive pas à le faire:cry:
Pourriez vous me donner un coup d'aide?
Merci!
Voici un exemple pour mieux assimiler:
soit
6 taches : j1, j2, j3, j4, j5, j6
3 machines : m1, m2, m3
durée d'exécution : 3, 6, 1, 2, 10, 4
d : 12, 5, 7, 8, 10, 6, 18
r(date de début de la tache, nécessaire pour placer les taches sur la machine) : 0, 1, 6, 3, 9, 12

1)
séquence de tache (3,4,1,6,2,5)
2)manuellement
sur m1 : les taches 3, 5
sur m2 : les taches 4, 2
sur m3 : les taches 1, 6

retards :
T1 :3-12<0->T1=0 (retard ne peut pas être négatif)
T2 : 10-5=5->T2=5
T3: 7-7=0
T4:5-10<0
T5:17-6=11
T6:7-8<0
T retards totaux: 5+11=16
21/08/2009, 16h29
Tristan Zwingelstein

Citation:

Envoyé par laureat

selon la formule donnée.

Ou ça ?
21/08/2009, 16h49
laureat

Citation:

Envoyé par laureat

(formule est la suivante : date de fin d'exécution de la tache "c" -date de fin au plus tard de la tache "d") : T= c -d.
23/08/2009, 17h02
cameleon65

Quand tu dis minimiser les retards totaux, c'est la solution optimale qu'il faut trouver ? Est-ce qu'il y a un type d'algorithme particulier qu'il faut utiliser ?
23/08/2009, 17h53
laureat

Citation:

Envoyé par cameleon65

Quand tu dis minimiser les retards totaux, c'est la solution optimale qu'il faut trouver ? Est-ce qu'il y a un type d'algorithme particulier qu'il faut utiliser ?

non
24/08/2009, 03h33
cameleon65

Si on fait ce que la règle dit, il suffit de mettre la tâche la plus petite du tri croissant que tu as fait dans la première étape à la machine qui a la moins de temps accumulé.

Donc, de façon itérative, tu fais:

Tant qu'il y a une tâche à placer
Trouver la machine qui a le moins de temps accumulé
Placer sur cette machine la tâche la plus courte qui n'a pas encore été assignée
Fin du tant que

Salut,

Merci pour votre réponse.
J'ai écris cet algorithme. Il me semble inefficace!
Des idées??

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
soit :
i:compteur tache
k=3: nombre de machine;
k:machine;
t(k): date de disponibilité de la machine;
t(k)=0 quelque soit la machine k;
J : {j1, j2, j3, j4, j5}ensemble de taches ordonnancées par ordre de priorité
tant que J<>0 faire
pour(i=0;i<2;i++) faire
placer les j1, j2 et j3 respectivement sur k1, k2 et k3;
corriger la date de disponibilité de la machine k1,k2 et k3;
enlever j1, j2 et j3 de J;
pour(i=3;i<5;i++)
chercher une machine k* disponible au plus tôt(min t(k));
placer j3 sur k*;
corriger la date de disponibilité de k*;
enlever j3 de J;
fait

Merci d'avance!

Voici mon idée:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/******************************
        Déclarations des types
*******************************/
typedef struct
{
	unsigned int tempsAccumule;	
}Machine;
 
typedef struct
{
	unsigned int duree;
	unsigned int finAuPlusTard;
}Tache;
 
/***************************************
        Déclarations des variables locales
****************************************/
unsigned int nombreMachines;
unsigned int nombreTaches;
 
unsigned int numeroMachineDisponible;
int tempsRetard;
 
Machine machines[nombreMachines];
Tache taches[nombreTaches];
 
/******************************
        Corp de la fonction
*******************************/
tempsRetardsTotaux = 0;
 
//Pour toutes les machines
Pour i allant de 0 à nombreMachines en pas de 1
	machines[i].tempsAccumule = 0;
Fin du pour
 
//Pour toutes les tâches à placer
Pour i allant de 0 à nombreTaches en pas de 1
 
	//Trouver la machine ayant le moins de temps accumulé
	numeroMachineDisponible = 0;
	Pour j allant de 1 à nombreMachines en pas de 1
		Si machines[j].tempsAccumule < machines[numeroMachineDisponible].tempsAccumule
			numeroMachineDisponible = j;
		Fin du si.
	Fin du pour.
 
	//Accumuler le temps sur la machine trouvée
	machines[numeroMachineDisponible].tempsAccumule += taches[i].duree;	
 
	//Accumuler le retard de la tâche aux retards totaux
	tempsRetard = taches[i].finAuPlusTard - (machines[numeroMachineDisponible].tempsAccumule + taches[i].duree);
	Si tempsRetard > 0
		tempsRetardsTotaux += tempsRetard;
	Fin du si.
 
Fin du pour

On peut utiliser des tableaux à la place des structures, mais j'ai préféré utiliser des strutures pour regrouper les attributs et donc faciliter la compréhension.

26/08/2009, 17h04
laureat

Merci pour cette idée géniale:ccool:.
Je vais essayer de la codé en c.
merci beaucoup.