Authors
Omar Souissi, Frederic Dugardin, Farouk Yalaoui,
Title
Méthodes exactes pour la résolution d'un problème d'ordonnancement Open-shop avec contraintes de ressources
In
MOSIM 2016
Year
2016
Indexed by
Abstract
Dans le présent papier nous considérons le problème d'ordonnancement dans un atelier Open-shop avec contraintes de ressources. La plupart des problèmes d'ordonnancement sont NP-dicile, les chercheurs ont ainsi favorisé en grande majorité le développement d'heuristiques et métaheuristiques au détriment des méthodes exactes. Dans un contexte où les calculateurs haute performance sont en amélioration continue, il redevient intéressant d'explorer des méthodes exactes. Ici, nous nous concentrons sur le développement de méthodes exactes pour la résolution d'un problème d'ordonnancement dans un atelier Open-shop. Nous développons d'abord un Programme Linéaire en Nombre Entiers (PLNE) accéléré en vue de l'optimation de la durée du flux total. Par la suite, nous exposons une nouvelle borne inférieure obtenu en optimisant la durée du flux total du problème Open-shop relaxé. Les résultats expérimentaux ont permis de valider les performances du PLNE accéléré en comparaison avec le PLNE original. Par ailleurs, nous avons montré que la relaxation lagrangienne du PLNE original produit une borne inférieure de bonne qualité.
Affiliations
Offprint