Version imprimable
Bonjour,
Pouvez-vous m'indiquer s'il existe un algo pour résoudre ce genre de pb : j'ai un ensemble de tâches T(i). Certaines tâches ont des contraintes et ne doivent être exécutées qu'après que d'autres tâches se soient terminées.
J'ai une durée d'exécution pour chaque tâche, et je peux exécuter au plus N tâches en parallèle.
Comment ordonnancer ces tâches de sorte que le temps total soit minimum ?
Merci pour votre aide.
Laly.
C'est un problème NP - complet. Un résultat théorique classique dû à Graham dit que n'importe quel ordonnement de liste (cela consiste à exécuter une tâche dès que possible) donne un résultat dont la durée est au plus 2-1/N fois celle de l'optimum. (N est dans ton message le nombre de tâche max qu'on peut exécuter en parallèle).
Pour avoir un bon ordonnancement en pratique, il peut être utile de faire un peu de recherche par voisinage pour améliorer un tel ordonnancement de liste.
Il doit exister une tonne et demi d'articles sur le net sur le sujet.
Je préconise google... car je suis pas en mesure d'expliquer maintenant comment on peut faire ca ! ;)
http://mathematiques.ac-bordeaux.fr/...htm#Exercice38
un exo traitant d'un truc semblable (algorithmes de flots minimum) est sur ce lien.
Merci bcp pour ces réponses qui vont me permettre de démarrer.
Par contre au niveau des méthodes Pert et MPM, je ne vois pas de limitation par rapport au nb max de tâches pouvant être exécutées concurremment. Mais je vais voir s'il existe une variation de ces algo me permettant de mettre rapidement qqchose en place.
Laly.
Effectivement, le PERT donne un ordonnancement qui peut avoir plus de N tâches en parallèle. A partir de là, il est possible de repérer un ensemble de plus de N tâches qui ont lieu en même temps puis de rajouter des précédences (de manière heuristique) entre quelques unes de ces tâches. Pour l'heuristique, on peut utiliser les marges.