Job shop Scheduling

**pseudocode** · 03/01/2007, 11h16

Bonjour,

je voudrais implementer en Java un algo de scheduling de type "Job Shop".

Je sais que c'est un probleme NP-Complet donc une approximation meme vague me suffira (enfin pas trop vague quand meme

).

Apres avoir recheché sur le Net, j'ai trouvé soit des equations obscures de manipulation de graphes

, soit des rumeurs et allusions a des algo genetiques. Moi je cherche un semblant d'algorithme (un peu documenté) dans un langage comprehensible (pascal, C, C++, java, ... meme en francais/anglais). Je publierai mon code s'il fonctionne.

Merci de votre aide et bonne journée a tous...

**mamelouk** · 03/01/2007, 13h38

Salut,
Ca doit etre la période en ce moment, car c'est le 3ème post sur ce sujet cette semaine ^^

Désolé je n'ai pas d'algo codé tout pret à te fournir, voici tout de meme ma contribution : http://www.developpez.net/forums/sho...d.php?t=255133

a+

ps: c'est le genre de problèmes si tu ne comprends pas la théorie, ne cherche meme pas à lire le code d'implémentation

**pseudocode** · 03/01/2007, 14h33

oups. désolé

J'ai cherché dans le forum "scheduling" mais j'etais passé a coté du "timetabling"

**FrancisSourd** · 03/01/2007, 14h41

Attention le job-shop et le time-tabling, ce n'est pas tout à fait la même chose. Il y a eu un sujet sur le jobshop il y a un mois:
http://www.developpez.net/forums/sho...d.php?t=249324

**pseudocode** · 03/01/2007, 14h43

mega-désolé

j'ai pas vu celui la non plus... arf! j'ai pas non plus pensé à "jobshop" en un seul mot !

**Jobshop** · 26/01/2007, 18h19

Bonjour je suis un etudiant en master recherche je travaille sur les même problems tu dois lire la parti théorique sinon tu t'on sort pas.
même je vais codé en java
allez bonne chance@+

**pseudocode** · 28/01/2007, 18h38

Envoyé par Jobshop

Bonjour je suis un etudiant en master recherche je travaille sur les même problems tu dois lire la parti théorique sinon tu t'on sort pas.
même je vais codé en java
allez bonne chance@+

En fait j'ai changé de technique. J'ai écrit des regles de scheduling spécifiques a mon environnement et je fais du backward-chaining pour résoudre mon probleme.

**blanchess** · 18/03/2011, 17h28

bonjour,

c'est vrai que c'est tard man question, mais j'ai le meme problème.
SVP, est-ce que vous avez trouvé une solution a ce problème?

Si oui prière de m'envoyer la solution
Merci

**nono_31** · 19/03/2011, 11h05

Bonjour,

Si tu cherches une méthode d'approximation :

Les heuristiques de liste ou permutation sont faciles à implémenter (priority dispatching rule).
Sinon, l'heuristique de la machine goulet est dédié au job-shop, mais plus compliquée.

Sinon, l'heuristique de la machine goulet est dédiée au job-shop.

Elles sont classiques en ordonnancement.

**blanchess** · 28/03/2011, 13h00

merci a ta réponse nono 31
je crois c'est mieux et + facile de choisir les heuristiques de liste ou de permutation
mais le problème c'est quelle la règle de priorité le + adopté dans un tel problème(priority dispatching rule).Car mon projet ca sera paramétrable
qui permet de résoud le problème de planification du production dans l 'industrie(flowshop,jobshop,production a la commande,production au stock).donc mon problème "Quelle la règle le + adopté pour chaque problème?

**nono_31** · 28/03/2011, 13h12

Bonjour,

Par définition, les heuristiques de liste prennent comme argument une liste des tâches ordonnées selon une règle de priorité.
Même sur des problèmes de taille conséquentes, leur exécution est très rapide.
Je te recommande donc d'appliquer à chaque fois plusieurs règles, voire d'ajouter un élément de randomisation, puis de prendre la meilleure solution.

Ces heuristiques offrent souvent une garantie théorique sur les problèmes pures (sans contraintes additionnelles).

Je te conseille deux références (qui commence certes à dater un peu) :
Guéret, C. & Prins, C. Classical and new heuristics for the Open-Shop problem EJOR (European Journal of Operational Research), 1998, 107, 306-314

Adams, J.; Balas, E. & Zawack, D. The Shifting Bottleneck Procedure for Job Shop Scheduling MANAGEMENT SCIENCE, 1988, 34, 391-401

Bonne chance,
Arnaud