idée algorithme

Forums

» » »

idée algorithme

Posté le 21-08-09 à 16:44

Posté par reporteur

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

cet algorithme est efficace??

Posté le 25-08-09 à 16:11

Posté par reporteur

Bonjour,
voici le problème : il s'agit de placer n taches sur m machines selon la règle suivante placer la tache suivante sur la machine la plus disponible. 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 me parait ne pas être optimal!
Des commentaires??Des idées??

Citation :
i:compteur tache
M =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 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

Avec mes remerciements

*** message déplacé ***

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster

Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.