Abstract FR:

Le travail présenté dans cette thèse s’est déroulé dans le cadre d’une convention CIFRE entre le Laboratoire d’Informatique de l’Université François-Rabelais de Tours et la société Vitalicom. Ce travail porte sur la planification de personnel dans les centres d’appels (ou centres de contacts clients). La planification de personnel est devenue un enjeu économique très important, surtout dans les sociétés de services telles que les centres d’appels. En effet, la réactivité dans ce secteur est très importante, car il faut répondre au client dans des délais très courts. Toutefois, la planification de personnel dans un centre d’appels ne se résume pas à la création des horaires des employés. Le client envoie les prévisions d’appels au centre qui doit ensuite planifier le personnel afin de répondre à ces appels, tout en assurant une certaine qualité. Deux problèmes majeurs se profilent alors : -Déduire le nombre d’agents requis pour répondre aux appels, période par période. Ce problème est appelé dimensionnement. - Créer les horaires des agents sur un horizon d’une semaine. Ce problème est le Shift Design Problem. Le but de cette thèse est de résoudre ces problèmes de manière à obtenir un outil complet d’aide à la planification de personnel. La thèse est organisée de la façon suivante. Le chapitre 1 définit le contexte des centres d’appels. De nombreux aspects de cette industrie sont évoqués. Une méthode de planification en quatre phases est proposée. Elle sera suivie dans les chapitres suivants. Le chapitre 2 présente un état de l’art sur les deux problèmes majeurs traités dans cette thèse : le dimensionnement et la planification de personnel. Pour le problème de dimensionnement, les lois les plus usuelles sont données, ainsi que les formules de calcul de la qualité de service. Ensuite, des extensions du modèle de base sont données, avec leurs algorithmes respectifs. Pour le problème de planification de personnel, une notation des problèmes est proposée, inspirée de la notation à trois champs des problèmes d’ordonnancement. Ensuite, diverses méthodes de résolution de la littérature sont présentées, en expliquant pour chacune les inconvénients qui empêche d’appliquer cette méthode au problème qui nous concerne directement. Le chapitre 3 traite du dimensionnement des centres d’appels. Une modélisation déterministe est proposée et justifiée. Ensuite plusieurs méthodes de résolution sont proposées : un programme linéaire en nombre entiers, un programme par contraintes, des algorithmes de listes et des descentes locales. Des tests sont présentés et les méthodes de résolution sont comparées entre elles. Enfin, un moteur de simulation est présenté, ainsi que la simulation des résultats fournis par les algorithmes. Le chapitre 4 traite de la création des horaires des employés. Le problème est tout d’abord modélisé à l’aide de la PLNE et de la PPC. Ensuite deux méthodes heuristiques de résolution sont proposées : une méthode Tabou et une méthode de recherche sur de multiples voisinages, appelée Runner. Les méthodes sont testées et comparées. Enfin, le chapitre 5 traite de l’outil d’aide à la planification. Le problème de l’annualisation du temps de travail est d’abord traité. Un PLNE est mis en place pour résoudre ce problème. Ensuite, un outil de gestion de contraintes personnelles des employés est mis en place. Enfin, un exemple complet de planification est déroulé entièrement.