Résolution de problèmes de tomographie discrète : application à la planification du personnel
Institution:
Paris, CNAMDisciplines:
Directors:
Abstract EN:
This thesis consists in developing the study of discrete tomography problems. My contributions have both theoretic and experimental aspects which are illustrated by applications in workforce scheduling and in image reconstructing. - Theoric contributions. We have determined the complexity and proposed polynomial algorithms to solve general cases of the following problems : Tiling with dominoes and bars. Reconstructing binary matrices under adjacency constraints. Reconstructing binary matrices under alternate periodicity constraints. Reconstructing colored tables. - Experimental contributions. We have proposed an original approach to solve the problem of days-off scheduling with 2-3 or 3-4 consecutive days off per week. . We have proposed an heuristic to help in reconstructing grey-scale images. Finally, we open some theoretic perspectives to study other discrete tomography problems.
Abstract FR:
Ce travail de thèse est une contribution à l'étude des problèmes de tomographie discrète. Ces contributions sont à la fois théoriques et pratiques, illustrées par des applications à la planification de personnel et à la reconstruction d'images discrètes. - Au niveau théorique, nous avons déterminé la complexité et proposé des algorithmes polynomiaux pour résoudre des cas assez généraux pour les problèmes suivants : Packing et pavage par des dominos et des barres. Reconstruction de matrices binaires avec contraintes d'adjacence. Reconstruction de matrices alternées périodiques. Reconstruction de tableaux colorés. Au niveau pratique : nous avons proposé une approche originale pour le problème de planification de personnel avec 2-3 ou 3-4 jours de repos consécutifs par semaine. Nous avons proposé une heuristique pour aider à la reconstruction des images avec niveaux de gris. Nous ouvrons aussi de nouvelles perspectives pour l'étude des problèmes de tomographie discrète.