Grant: Collaborative Research and Development Grants

Avec AD OPT (récemment acquise par Kronos), nous avons participé au développement de deux familles de logiciels d'optimisation d'horaires de personnel : ShifLogic pour des employés travaillant sur des quarts et effectuant des activités continues (ex. : caissier), et Altitude pour les équipages aériens effectuant des tâches ponctuelles (ex. : piloter un avion durant un vol). Ce projet développera des méthodes d'optimisation en vue de généraliser les optimiseurs d'AD OPT pour répondre aux nouvelles opportunités rencontrées dans le vaste réseau de distribution de Kronos. Le premier objectif est de traiter les problèmes combinant des activités continues et des tâches ponctuelles. La construction d'une première bonne solution sera facilitée en développant un analyseur des goulots d'étrangle- ment du problème. Il utilisera un modèle mathématique approximatif pour repérer les périodes de temps où la disponibilité d'employés pour une ou plusieurs activités est insuffisante ou serrée. La solution initiale sera améliorée avec une approche qui combinera des méthodes tabou, de recherche à voisinages variables, de programmation mathématique et dynamique pour produire rapidement de bonnes solutions pour des problèmes hebdomadaires de plusieurs centaines d'employés. Un analyseur de solution sera développé pour identifier les parties de la solution à améliorer. Certaines améliorations seront obtenues en résolvant des problèmes mathé- matiques pour lesquels il existe des algorithmes rapides : plus court chemin, problème d'affectation, ... Ces algorithmes permettront de choisir la meilleure solution parmi un nombre exponentiel de solutions voisines de la solution courante avec un nombre d'opérations beaucoup plus petit que le nombre de voisins. Les autres objectifs portent sur le traitement d'extensions du problème : des tâches déplaçables dans le temps, des contraintes de préséance entre des tâches, la possibilité d'interrompre certaines tâches en tenant compte de règles et de coûts, le travail par équipe avec des exigences d'expertise dans l'équipe. Les méthodes d'optimisa- tion pour le problème de base et ses extensions seront développées pour la planification et les opérations.