Discussion :

[laureat]

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 :

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


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 :


Merci d'avance;

[CedricMocquillon]

Bonjour,

Ton problème se note dans la littérature (notation de Graham): P|r_i|C_max : problème à machine parallèles identiques avec dates de début au plus tôt et minimisation de la date de fin. Sur le site de Peter Brucker, tu peux trouver la complexité de nombreux problèmes, d'après ce site, le problème P||C_max est NP difficile et tu as même la référence bibliographique:
M.R. Garey and D.S. Johnson.
``Strong'' NP-completeness results: motivation, examples, and implications.
J. Assoc. Comput. Mach., 25(3):499-508, 1978.
Elle devrait t'aider à trouver une bonne méthode heuristique ou exacte dans la littérature (science direct, acm, ieee, ...). Tu peux également voir sur le site e-ocea qui propose plusieurs références bibliographiques pour différents types de problèmes d'ordonnancement.