LIP6 1997/005

Résolution du problème d'ordonnancement de type Job-Shop généralisé par des heuristiques dynamiques

F. Ghedjati, J.-Ch Pomerol

LIP6 1997/005: Rapport de Recherche LIP6 / LIP6 research reports
25 pages - Juin/June 1997 - French document.

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

Titre français : Résolution du problème d'ordonnancement de type Job-Shop généralisé par des heuristiques dynamiques
Titre anglais : Dynamical Heuristics for the generalized Job-Shop scheduling problem

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

Abstract : This paper proposes a solution of the generalized job-shop factory scheduling problems by several original of static and dynamic heuristics relying on the potential load of the machines. On the one hand, we consider, unrelated parallel machines which can execute the operations of the different jobs, and, on the other hand, any precedence contraints between the operations is allowed. The objective of the scheduling is to minimize the total duration of all the jobs, i.e. to minimize the Cmax. This problem is NP-Hard. Experimental results using different types of data, taken from the literature or randomly generated benchmarks are provided. Our approach allows a satifactory resolution of relatively important problems in a raisonable time.

Mots-clés : Ordonnancement, Job-shop généralisé, Machines non identiques en parallèle, Gamme linéaire et non linéaire, heuristiques dynamiques

Key-words : Scheduling, Generalized job-shop, Unrelated parallel machines, Linear and non-linear process rooting, Dynamical heuristics

Publications internes LIP6 1997 / LIP6 research reports 1997

Responsable Éditorial / Editor
webmaster@lip6.fr