idée algorithme d' affectation

Version imprimable

20/08/2009, 20h42
laureat

idée algorithme d' affectation

Salut,

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, 19h24
laureat

il n' y a aucune personne qui peut me donner un petit coup d'aide
:cry:

Bonsoir,
J'ai pensé à plusieurs idée.
Voici une

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
i:compteur tache
M =3: nombre de machine;
k:machine;
t(k): date de disponibilité de 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 m1, m2 et m3;
corriger la date de disponibilité de la machine m1,m2 et m3;
enlever j1, j2 et j3 de J;
pour(i=3;i<5;i++)
chercher une machine m* disponible au plus tôt(min t(k));
placer j3 sur m*;
corriger la date de disponibilité de m*;
enlever j3 de J;
fait

Que pensez vous pour cet algorithme et voyez vous une optimisation?