Genetic algorithms for the job-shop scheduling problem with parallel machines and precedence constraints : heuristic mixing method

F. Ghedjati

LIP6 1998/013: Rapport de Recherche LIP6 / LIP6 research reports
10 pages - Mars/March 1998 - Document en anglais.

PostScript : 103 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : 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
Titre anglais : Genetic algorithms for the job-shop scheduling problem with parallel machines and precedence constraints : heuristic mixing method

Résumé : 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.

Abstract : In this paper, we are interested, in the generalized job-shop scheduling problem with several unrelated parallel machines and precedence constraints (corresponding to linear and non-linear process routings) between operations of the job. The objective is to minimize the maximum completion time (Cmax). We propose an original resolution method based on genetic algorithms that we call heuristic mixing method, where crossovers mixe a specific heuristics designed for the considered problem. After a description of the problem and of the resolution method, we present experiment results.

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

Key-words : Scheduling, Generalized job-shop, Unrelated parallel machines, Linear and non-linear process routings, Genetic algoritms, heuristic mixing method

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr