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

Résumé : 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.
Type de document :
Communication dans un congrès
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
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00688219
Contributeur : Olivier Guyon <>
Soumis le : mardi 17 avril 2012 - 09:55:54
Dernière modification le : lundi 9 avril 2018 - 09:34:01
Document(s) archivé(s) le : mercredi 18 juillet 2012 - 02:21:50

Fichiers

Identifiants

  • HAL Id : emse-00688219, version 1

Citation

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〉

Partager

Métriques

Consultations de la notice

325

Téléchargements de fichiers

272