Abstract FR:

La reconnaissance croissante des enjeux économiques et sociaux liés à une gestion efficace de la ressource travail motive de nombreuses recherches et applications sur la planification d'horaires. L'adéquation d'effectifs à une charge variable et étendue au-delà des plages de travail individuelles, ainsi que l'aménagement des jours de travail et de repos, constituent des problèmes fortement combinatoires qui requièrent l'utilisation de techniques d'optimisation. L'objet de cette thèse est de caractériser les diverses situations de planification, de synthétiser la multitude d'approches présentées dans la littérature, de modéliser et résoudre efficacement certains problèmes complexes de planification d'horaires. Nous nous intéressons en particulier au problème de construction de vacations couvrant une courbe de charge à cout minimal. Après avoir comparé différentes modélisations et approches de résolution, nous montrons expérimentalement, sur des instances de grande taille, que ce problème formulé comme un problème de couverture d'ensembles généralisé est facilement résolu par programmation linéaire en nombres entiers (plne). Nous caractérisons même certaines classes polynomiales de ce problème. Nous étudions ensuite le problème central d'élaboration de grilles de travail pour lequel les performances de la plne et de la programmation par contraintes (ppc) sont également comparées. Finalement, nous élaborons une méthodologie de décomposition d'un problème global de planification associant les techniques de plne et ppc. Cette méthodologie est implémentée et validée dans le cadre d'applications réelles.