problème d'algorithme d'ordonnacement
Bonjour,
voici un petit problème d'algorithmique : je souhaite placer n taches sur m machines selon la règle suivante placer la tache suivante sur la machine la disponible plus tot. On connait la date de début souhaité de chaque tache. Objectif minimiser la date de fin d'exécution de la dernière tache de projet.
J'ai écris cet algorithme. Il ne me semble pas efficace!
Avez-vous une autre idée d'algorithme pour traiter ce problème?
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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 |
voici un exemple :
http://i85.servimg.com/u/f85/14/25/90/60/tablea16.jpg
Liste de priorité des taches J: 3, 4, 1, 5, 2(par ordre de durée d'exécution croissant).
Après, il s'agit de placer la tache qui a la plus petite durée d'exécution sur
la machines disponible plus tot tant que J <> 0 pour déterminer la séquence
d'ordonnancement optimale.
la solution est représentée par ce diagramme :
http://i85.servimg.com/u/f85/14/25/90/60/gantt10.jpg
Merci d'avance;
