LIP6 1997/005

• Rapports de recherche
  Résolution du problème d'ordonnancement de type Job-Shop généralisé par des heuristiques dynamiques
• F. Ghedjati, J.-Ch.Pomerol
• 25 pages - 12/06/1997- document en - http://www.lip6.fr/lip6/reports/1997/lip6.1997.005.ps.gz - 50 Ko
• Contact : Fatima.Ghedjati (at) nulllaforia.ibp.fr, Valerie.Mangin (at) nulllip6.fr
• Ancien Thème : SYSDEF
Le présent article propose une résolution du problème d’ordonnancement d'ateliers de type "job-shop généralisé" par plusieurs méthodes heuristiques statiques et dynamiques originales tenant compte de la charge potentielle des machines au fur et à mesure de la construction de la solution. Nous considérons, d'une part, des machines non identiques (ou non reliées) en parallèle pouvant effectuer les opérations de différentes pièces et, d'autre part, des contraintes de précédence quelconques entre les opérations. L’objectif de l'ordonnancement est la minimisation de la durée totale de l'exécution de toutes les pièces, autrement dit la minimisation du Cmax. Ce problème est NP-difficile. Des expérimentations ont été effectuées avec divers types de données issues de la littérature ou générées aléatoirement. Notre approche permet de traiter d'une manière satisfaisante des problèmes relativement importants en des temps raisonnables.
• Mots clés : Ordonnancement, Job-shop généralisé, Machines non identiques en parallèle, Gamme linéaire et non linéaire, heuristiques dynamiques
• Directeur de la publication :