Discussion :

[laureat]

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

[Tristan Zwingelstein]

selon la formule donnée.

Ou ça ?

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

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

[laureat]

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

[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

[laureat]

Salut,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[cameleon65]

Voici mon idée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[laureat]

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