Approche évolutionniste contrôlée pour les problèmes d’ordonnancement : cas du Job-shop flexible

 

Imed KACEM, Slim HAMMADI, Pierre BORNE

 

Ecole Centrale de Lille, LAIL-URA CNRS D 1440, BP 48, 59651 Villeneuve d'Ascq Cedex-France

imed.kacem@ec-lille.fr, Hammadi@ec-lille.fr, p.borne@ec-lille.fr,

 

 

 

Formulation du problème--Le problème est d’organiser la réalisation de N jobs sur M machines. L'ensemble des machines est noté U. Chaque job j représente un nombre n_j opérations ordonnées. Chaque opération i d'un job J_j (notée O_i,j) peut être réalisée sur un ensemble de machines U_i,j Í U.

Dans le cas d'un problème totalement flexible U_i,j = U pour tout i et j.

Dans le cas d'un problème partiellement flexible, il existe au moins (io, jo) / U_io,jo Ì U.

L'affectation d'une opération O_i,j sur une machine M_k  U_i,j entraîne l'occupation de cette machine pendant une durée d _i,j,k .

Dans ce problème, nous faisons les hypothèses suivantes :

·        toutes les machines sont disponibles à la date t = 0 ;

·        tous les jobs peuvent être commencés à date t = 0 ;

·        l'ordre des opérations pour chaque job est fixé dès le départ et ne peut pas être modifié (contrainte de précédence dans la gamme).

·        Une machine ne peut exécuter à la fois qu'une seule opération.

La résolution d'un tel problème nécessite donc l'affectation de chaque opération O_i,j sur une machine M_k  U_i,j , ensuite le calcul des dates t_i,j de début d'exécution.

 

Résumé --- Dans cet article nous présentons une nouvelle méthode pour résoudre un problème d'ordonnancement de type Job-shop (partiellement et totalement flexible). L'objectif de cette méthode est d'optimiser conjointement les deux critères classiques :

·        le maximum des temps de fin d'exécution " Makespan",

·         les charges des machines.

La première étape de cette approche permet de résoudre le problème d’affectation de ressources et de construire un modèle idéal d’affectations (schéma d’affectations).

La deuxième étape est une approche évolutionniste contrôlée par le modèle des affectations (généré dans la première étape). Dans cette approche, nous appliquons des manipulations génétiques avancées pour améliorer la qualité des solutions.

 

Mots clés --- Job-shop Flexible, Ordonnancement, Affectation, Approche par localisation, Algorithme évolutionniste contrôlé, Manipulation génétique.