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

Nous considérons un problème couplant ordonnancement de production et planification d\u27agents. 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\u27un 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\u27optimisation 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\u27agents et un problème de job-shop à contraintes de disponibilité. Des méthodes de génération d\u27inégalités valides en pré-process (notamment du probing) ont en outre été étudiées. Notre approche s\u27avère particulièrement adaptée à la problématique ; ses résultats dominent en effet ceux obtenus avec l\u27un des meilleurs solveurs commerciaux actuels (Ilog Cplex 12.1) et ceux obtenus avec les méthodes décrites dans la littérature