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.