Description
Date depot: 1 janvier 1900
Titre: Optimisation et aide à la décision pour la planification de la numérisation du patrimoine
Directeur de thèse:
Christophe GONZALES (LIP6)
Directrice de thèse:
Safia KEDAD-SIDHOUM (CEDRIC)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
La numérisation de masse de documents est un enjeu majeur de la société de l'information, d'une part parce qu'elle permet de sauvegarder des documents périssables (sous forme papier) et d'autre part car elle permet leur traitement et leur indexation automatique. Les entreprises travaillant dans ce domaine traitent des quantités de documents très importantes (à titre d'exemple, rappelons que Google vise la numérisation de 15 millions de livres en six ans) et ont donc un besoin croissant d'outils sophistiqués d'aide à la décision pour optimiser la planification des tâches sur leurs chaînes de numérisation. Plusieurs facteurs rendent cette optimisation délicate à réaliser. Tout d'abord, l'hétérogénéité des documents à traiter induit une certaine complexité dans la chaîne de numérisation, en particulier lorsqu'un certain niveau de qualité est exigé (par exemple, la Bibliothèque Nationale de France demande un résultat conforme à l'original à 99,985%). Ensuite, la diversité géographique et technique des opérateurs impliqués dans la chaîne de numérisation, ainsi que les contraintes inhérentes à chacun, accroît encore cette complexité. En outre, il n'existe pas un unique critère d'évaluation pour l'ordonnancement des tâches, mais de multiples critères potentiellement conflictuels : critères économiques liés aux coûts de numérisation, critères de qualité des traitements réalisés, critères liés à la bonne répartition des ressources, pénalités de retard, etc.
Cette thèse a pour but la conception d'outils d'optimisation et d'aide à la décision capables de proposer des ordonnancements efficaces pour planifier les tâches de numérisation sur des gros volumes de données. En particulier, ces outils doivent permettre de distribuer de manière fluide les tâches vers les bons automates et/ou vers les bons opérateurs. Par ailleurs, ils doivent prendre explicitement en compte la dimension dynamique de la chaîne de numérisation. Pour ce faire, ces outils doivent retourner des ordonnancements « robustes », autrement dit relativement stables par rapport à l'arrivée de nouveaux documents à numériser et à leurs contraintes afférentes (dates de délivrables, contraintes de qualité, etc).
Plus précisément, cette thèse définira rigoureusement d'un point de vue mathématique le problème à traiter. En particulier, on s'attachera à caractériser les différents critères d'évaluation pertinents pour la numérisation du patrimoine (coûts de numérisation, pénalités de retard, etc), ainsi que les contraintes spécifiques à ce type de problème (caractéristiques des tâches de numérisations telles que normes et standards, identification des ressources disponibles telles que automates et/ou opérateurs, etc). Une étude de complexité des problèmes identifiés sera menée. Elle visera notamment à isoler des sous-problèmes polynomiaux. En ce qui concerne la résolution des problèmes ainsi modélisés, on s’efforcera de développer des algorithmes exacts et/ou approchés pour l’optimisation monocritère ou multicritère du workflow. Les méthodes développées viseront d'abord à obtenir des séquences efficaces de tâches de numérisation, qui pourront ensuite faire l'objet d'une démarche plus générale d'étude de flexibilité et de robustesse des ordonnancements ainsi calculés. Compte tenu de la volumétrie des données à traiter, on pourra en outre s’intéresser à la problématique de la sélection d’un sous-ensemble de tâches à ordonnancer dont la réalisation est particulièrement prioritaire pour atteindre les objectifs fixés. Les technologies qui seront mises en jeu sont propres aux domaines de l'aide à la décision, de l’optimisation multicritère et de l’ordonnancement.
Références
Lucie Galand, Patrice Perny et Olivier Spanjaard (2008) 'Optimization of the Choquet integral in multicriteria combinatorial problems'. Dans 19th International Conference on Multiple Criteria Decision Making.
Christophe Gonzales, Patrice Perny et Segio Queiroz (2008) GAI-Networks: optimization, ranking and collective choice in combinatorial domains. Foundations of Computing and Decision Sciences. Vol.33, N°1, pp.3—24.
Safia Kedad-Sidhoum, Yasmin Rios Solis et Francis Sourd (2008) 'Lower bound for the earliness-tardiness scheduling problem on parallel machines with distinct due dates'. European Journal of Operational Research, N°3, pp. 1305--1316.
V. T'kindt et J.C Billaut (2002) 'Multicriteria Scheduling'. Springer Verlag, Berlin.
Pascal Van Hentenryck et Russell Bent (2006) 'Online Stochastic Combinatorial Optimization'. MIT Press.
T.E. Vollman, W.L. Berry, D.C. Whybark (2004) 'Manufacturing Planning and Control Systems For Supply Chain Management : The definitive guide for professionals'. McGraw-Hill.
Doctorant.e: Seddik Yasmina