We first survey the main approaches for solving employee, school and sports timetabling problems and discuss several specific issues of each of these problems classes. Then we present a couple of applications and related solutions approaches for employee and sports timetabling respectively.

The first application deals with the nurse rostering for a ward of an Italian hospital: here it is required to consider both holidays planning and parametric contractual constraints, but no cyclic schedules and corresponding weekly patterns.

The second application deals with the scheduling of the Italian Major Football League (the so-called "Serie A"): here we search for a double round robin tournament schedule that takes into account typical requirements such as conditions on home-away matches, specific requests of the Italian Football Association such as twin-schedules for teams belonging to the same home-town and additional requirements related to cable TV broadcasting.

L'exposé se donne pour objectif de décrire les grandes lignes d'un outil générique permettant de modéliser et de résoudre des problèmes complexes de planification de personnel dans les secteurs d'activités relatifs à la grande distribution, outil développé au sein de la société TempoSoft dans le cadre d'un progiciel intranet et multi-plateforme, dédié à la gestion du temps de travail.

Nous nous attacherons à montrer comment les impératifs de flexibilité et de robustesse ont été pris en compte dans l'architecture de cet outil. Un objectif central de la planification est que l'ensemble des taches planifiées pour chaque activité couvre son besoin en effectif (la charge). Ainsi, seront introduites les différentes notions de charge (fixe, mobile, mixte, insécable), les contraintes liées aux activités, les contraintes et objectifs divers liés aux ressources humaines. La richesse et variabilité des réglementaires rencontrés ne permettent pas de se contenter d'une approche « boite à cocher » ou « dictionnaire de contraintes », et sont gérées dans notre outil par un vrai langage de modélisation, graphique pour l'essentiel. Nous parlerons globalement du processus de résolution, et particulièrement du coeur du moteur d'optimisation, basé sur un algorithme de Branch and Price, autrement dit une génération de colonnes pilotée par un Branch and Bound. Le problème esclave étant géré par des techniques de programmation dynamique et de programmation par contraintes.

Derrière le vocable « Optimisation de l'organisation et de l'affectation des ressources humaines » se cache en réalité une véritable mosaique de problèmes, différents en fonction de l'activité, variés au sein d'une meme entreprise mais aussi inter-dépendants.

Aussi variées qu'elles soient, les problématiques associées à la planification des ressources humaines n'en ont pas moins des enjeux communs. Enjeux sociaux tout d'abord, car derrière la remise en cause de l'organisation du travail se cache le maintien des avantages acquis, le confort des agents, la renégociation des règles du jeu avec les partenaires sociaux. Enjeux économiques ensuite car dans un marché concurrentiel, l'objectif de l'employeur est de maintenir ou augmenter la productivité de son entreprise, et qu'une meilleure organisation des ressources humaines est un moyen significatif d'y parvenir. Enjeux en termes de qualité de service rendu enfin, car une meilleure organisation des horaires est pour l'entreprise une voie privilégiée dans la recherche d'une meilleure satisfaction du client, voire d'une extension de son marché.

Un panorama général des problématiques rencontrées dans le domaine de l'optimisation des ressources humaines sera dressé, ainsi que d'approches permettant d'offrir un support en aide à la décisison dans ce domaine. L'exposé sera illustré par des exemples réels rencontrés au cours des 20 années d'expérience d'EURODECISION en optimisation et planification des ressources.

Le problème de planification de jours de repos (PPR) consiste à affecter les jours de travail et les jours de repos aux employés tout en respectant la charge et les contraintes de placement de repos. La charge représente le nombre d'employés présents par jour. Les contraintes de placement de repos indiquent le nombre minimum de repos hebdomadaires, les couples de repos, les repos mensuels, les quotas de week-ends en repos, etc.

Dans les problèmes traités précédemment, il n'était pas question du nombre de jours de travail par employé, c'est-à-dire, on ne s'intéressait qu'à minimiser l'effectif et à élaborer des emplois du temps non nominatifs. Ainsi selon les besoins, on cherchait le personnel pouvant les satisfaire.

Nous traitons le problème P23R qui consiste à affecter les jours de travail et les jours de repos aux employés sous différentes stratégies de placement de repos. L'effectif est composé par m employés e(i), i=1,...,m, ayant les memes qualifications. L'horizon de planification est composé de W semaines. v'(k,j) employés doivent travailler le jour d(j) de la semaine w(k) pour j=1,...,7 et k=1,...,W. Chaque employé e(i) travaille au total h'(i) jours et a droit à deux jours (2-RC) ou trois jours (3-RC) de repos consécutifs par semaine.

Comme beaucoup d'entreprises de transport, la SNCF répond aux besoins de ses clients en mobilisant des agents 24 heures sur 24, 365 jours par an. La planification d'une partie de son personnel sédentaire (par opposition au personnel roulant) s'effectue à l'aide de roulements, concus pour répondre à une charge de travail considérée identique chaque semaine de l'année.

Au cours de l'exposé nous présenterons deux modélisations du problème sous forme de programmes linéaires en nombres entiers exploitant, pour l'une, des variables journalières, et, pour l'autre, des motifs pré-construits sur une semaine. Les roulements générés doivent satisfaire des contraintes diverses sur le nombre et le placement des jours de repos (notamment pour les repos du weekend) et sur la durée des périodes de travail et de repos. Les souhaits des agents et du management sont pris en compte dans la fonction objectif. Des résultats experimentaux et un outil d'aide à la conception de roulement en ligne basé sur la deuxième formulation seront présentés.