Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

idée algorithme

Posté par
reporteur
21-08-09 à 16:44

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

Posté par
reporteur
cet algorithme est efficace?? 25-08-09 à 16:11

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



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !