Séparation et Evaluation pour le problème d’ordonnancement avec blocage

 

Abdelhakim Ait Zai, Abdelkader Bentahar, Hamza Bennoui,Mourad Boudhar et Yazid Mati
Faculté d’Electronique et d’Informatique, Département d’Informatique, 
USTHB, BP 32 El Alia Alger, Algérie.
Faculté de Mathématiques, Département de Recherche Opérationnelle,
USTHB, BP 32 El Alia Alger, Algérie.
Université d’Elkassime Arabie Saoudite.

 

Résumé : Nous traitons, dans ce papier, du problème d’ordonnancement Job shop avec blocage connu pour être NP-difficile. Après une présentation du problème posé, nous proposons de le résoudre d’une manière exacte en utilisant une méthode par séparation et évaluation SEP. Pour obtenir une solution optimale en un temps raisonnable, nous avons amélioré la méthode en utilisant une technique de séparation originale basée sur les graphes alternatifs. Nous avons utilisé aussi deux méthodes différentes pour l’évaluation d’une solution de la méthode SEP. Dans la dernière partie de ce papier, nous discutons les résultats des deux méthodes.


Mots clés : Job shop, blocage, séparation et évaluation, graphe alternatif. 

 

Télécharger l'article