Branch and Bound hybride pour un problème de job-shop soumis à des contraintes de ressources humaines - Mines Saint-Étienne
Conference Papers Year : 2012

Branch and Bound hybride pour un problème de job-shop soumis à des contraintes de ressources humaines

Abstract

Nous considérons un problème couplant ordonnancement de production et planification d'agents. On se place ainsi dans un atelier où la production à réaliser requiert divers types de machines dans des séquences variées de type job-shop. Chaque machine nécessite pour son utilisation la présence d'un employé qualifié à son pilotage. Les ressources humaines sont assujetties à des contraintes légales restreignant leur disponibilité. La production doit être entièrement ordonnancée et le critère d'optimisation retenu est la minimisation des coûts salariaux. Pour résoudre ce problème, nous avons développé une méthode exacte hybridant approche arborescente de type Procédure de Séparation et Evaluation Séquentielle et technique de génération de coupes de réalisabilité. Cette méthode exploite la décomposition naturelle du problème global en deux sous-problèmes : un problème de planification d'agents et un problème de job-shop à contraintes de disponibilité. Des méthodes de génération d'inégalités valides en pré-process (notamment du probing) ont en outre été étudiées. Notre approche s'avère particulièrement adaptée à la problématique ; ses résultats dominent en effet ceux obtenus avec l'un des meilleurs solveurs commerciaux actuels (Ilog Cplex 12.1) et ceux obtenus avec les méthodes décrites dans la littérature.
Fichier principal
Vignette du fichier
ROADEF2012.pdf (312.96 Ko) Télécharger le fichier
slides.pdf (582.68 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Format Other

Dates and versions

emse-00688219 , version 1 (17-04-2012)

Identifiers

  • HAL Id : emse-00688219 , version 1

Cite

Olivier Guyon, Pierre Lemaire, Eric Pinson, David Rivreau. Branch and Bound hybride pour un problème de job-shop soumis à des contraintes de ressources humaines. 13ème congrès annuel de la Société française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF), Apr 2012, Angers, France. ⟨emse-00688219⟩
271 View
265 Download

Share

More