Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Collaborative Research and Development Grants

École Polytechnique de Montréal

$96,854.00

Fast optimization algorithms for complex personnel scheduling problems

EF 2020-21

Résumé
Kronos Canadian Systems Inc. commercializes the Workforce Scheduler software to more than 1,100 organizations across the world, including more than 100 in Canada. This software allows to determine the work shift schedules of employees in various domains including retail, healthcare, leisure and hospitality, and manufacturing. Personnel shift scheduling is a complex combinatorial optimization problem that involves determining for each available employee his working days, the exact shift to work on each working day, and the job(s) to perform in each shift, in order to cover at best the demand in employees for each job. At Kronos, this problem is solved by a mathematical-programming-based optimization algorithm whose core strategies have been developed many years ago. To make the algorithm more robust to the recently integrated complex features, we propose to develop in this project new core strategies, namely, a new decomposition algorithm to split the problem into subproblems, improvement algorithms for solving each subproblem, and a new shift enumeration algorithm. Our main objective is to conceive an efficient and robust algorithm that will be able to solve the practical problem instances encountered by Kronos' clients. To achieve this goal, we will perform mathematical modeling, data analysis, and methodological developments that will involve integer programming, local search, large neighborhood search, and machine learning among others. The successful results from this research will be integrated into the Workforce Scheduler software. Given that the proposed developments will be at the heart of this software, they will provide a commercial advantage to Kronos that will be in a position to offer an improved software capable of solving large and complex personnel scheduling problems. A Canadian company will thus benefit directly from the positive impacts of this project. Moreover, a large number of Canadian companies/organizations which already use Workforce Scheduler will also benefit indirectly from this project when they will gain access to the new software version. Finally, this project will finance the training of seven MSc, PhD and postdoc students.
Programme
Collaborative Research and Development Grants
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
530544-2018
Name nom
DESAULNIERS, Guy
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2018
Award amount
96854
Program id
CRDPJ
Program name en
Collaborative Research and Development Grants
Program name fr
Subventions de recherche et développement coopérative
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
520
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Production and operations management
Area of application fr
Production et gestion des opérations
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Installment
inst:3 - 3
Partie
1
Nb partie
3
Application title
Fast optimization algorithms for complex personnel scheduling problems
Keyword
NSERC
Application summary
Kronos Canadian Systems Inc. commercializes the Workforce Scheduler software to more than 1,100 organizations across the world, including more than 100 in Canada. This software allows to determine the work shift schedules of employees in various domains including retail, healthcare, leisure and hospitality, and manufacturing. Personnel shift scheduling is a complex combinatorial optimization problem that involves determining for each available employee his working days, the exact shift to work on each working day, and the job(s) to perform in each shift, in order to cover at best the demand in employees for each job. At Kronos, this problem is solved by a mathematical-programming-based optimization algorithm whose core strategies have been developed many years ago. To make the algorithm more robust to the recently integrated complex features, we propose to develop in this project new core strategies, namely, a new decomposition algorithm to split the problem into subproblems, improvement algorithms for solving each subproblem, and a new shift enumeration algorithm. Our main objective is to conceive an efficient and robust algorithm that will be able to solve the practical problem instances encountered by Kronos' clients. To achieve this goal, we will perform mathematical modeling, data analysis, and methodological developments that will involve integer programming, local search, large neighborhood search, and machine learning among others. The successful results from this research will be integrated into the Workforce Scheduler software. Given that the proposed developments will be at the heart of this software, they will provide a commercial advantage to Kronos that will be in a position to offer an improved software capable of solving large and complex personnel scheduling problems. A Canadian company will thus benefit directly from the positive impacts of this project. Moreover, a large number of Canadian companies/organizations which already use Workforce Scheduler will also benefit indirectly from this project when they will gain access to the new software version. Finally, this project will finance the training of seven MSc, PhD and postdoc students.