Discussion :

[wanagro]

Bonjour,

J'aimerai savoir si des personnes parmi vous connaissent cet algorithme de planification?

Disposez vous de sources (pseudo code ou autre) ou de références traitant de cet algorithme je suis preneur.


PS: google n'a pas été mon amis... Il m'a renvoyé vers des articles certes tres interressant mais d'un niveau mathématique trop élevé pour moi

[CedricMocquillon]

L'algorithme de Johnson est un algorithme permettant de résoudre optimalement et en temps polynomial le problème de flow-shop à deux machine pour le critère Cmax (noté F2||Cmax) (Cmax étant la date de fin du dernier travail sur la deuxième machine). Il n'est pas très compliqué puisqu'il suffit de trier tes jobs suivant pi1 et pi2 (pi1 est le temps d'exécution du travail i sur la première machine et pi2 le temps d'execution sur la deuxième). Voici un lien expliquant le raisonnement et donnant un algo:

http://www.ielm.ust.hk/dfaculty/ajay...T/johnson.html

[wanagro]

Il n'est peut etre pas adapté pour trouver une solution avec n taches sur n machines ?

Par Exemple si
La tache 1 utilise la machine A puis la C puis la D
La tache 2 utilise la machine B puis la A
La tache 3 utilise la machine A puis la B puis la C puis la D
etc...

[CedricMocquillon]

Heu... là c'est plus tout à fait le même problème, c'est plutôt de l'open-shop ce que tu décris et si tu cherches à minimiser le Cmax sans conditions particulières, c'est un problème NP-Difficile au sens fort:
http://www.mathematik.uni-osnabrueck...s/o_now/o_now/
Il te reste alors deux solutions: soit tu cherches une méthode exacte et tu devras passer par une méthode d'exploration par séparation/évaluation, soit tu cherches une méthode approchée. Dans les deux cas, tu peux chercher des articles scientifiques sur le web pour voire quelles sont les méthodes développées les plus efficaces.