LIP6 1998/013

• Rapports de recherche
  Algorithmes Génétiques pour le problème d'ordonnancement job-shop avec machines en parallèle et contraintes de précédence.: méthode par brassage d'heuristiques
• F. Ghedjati
• 10 pages - 16/03/1998- document en - http://www.lip6.fr/lip6/reports/1998/lip6.1998.013.ps.gz - 105 Ko
• Contact : Fatima.Ghedjati (at) nulllip6.fr
• Ancien Thème : SYSDEF
Nous nous intéressons dans cet article au problème d'ordonnancement d'ateliers de type job-shop généralisé. Ce problème comporte, d'une part, des machines non identiques en parallèle pouvant effectuer les opérations des 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. Pour une résolution approchée de ce problème, nous proposons une méthode originale basée sur les algorithmes génétiques que nous appelons brassage d'heuristiques où les croisements mélangent des heuristiques spécifiques au problème considéré que nous avons conçues. Après la description du problème et de la méthode de résolution utilisée, nous présentons les résultats expérimentaux.
• Mots clés : Ordonnancement, Job-shop généralisé, Machines non identiques en parallèle, Gamme linéaire et non linéaire, Algorithmes génétiques, brassage d'heuristiques
• Directeur de la publication : Valerie.Mangin (at) nulllip6.fr