Optimization methods for complex personnel shift scheduling problems

Kronos Canada Systems Inc.向世界各地的1100多个组织销售Workforce Scheduler软件，其中包括加拿大的107个组织。该软件允许确定不同领域员工的工作时间表，包括零售、医疗保健、休闲和酒店以及制造业。人员排班是一个复杂的优化问题，涉及确定每个可用员工的工作日、每个工作日的确切工作班次以及每个班次要执行的工作(S)，以便最多满足员工对每项工作的需求。在克罗诺斯，目前的优化算法旨在解决计划版本的人员调度问题。在这个项目中，我们建议增强其能力，并探索解决复杂版本的人员调度问题的替代算法，即需要在发生不可预见的事件时修改计划时间表的重新调度，考虑需求变化和潜在员工缺勤的稳健调度，以及考虑部门之间或站点之间可能的员工调动的多部门/多地点调度。我们的主要目标是开发一个有效的算法来解决每个问题变体的实际实例。为此，我们将进行数学建模、数据分析和方法开发。

Kronos Canadian Systems Inc. commercializes the Workforce Scheduler software to more than 1,100 organizations across the world, including 107 in Canada. This software allows to determine the work schedules of employees in various domains including retail, healthcare, leisure and hospitality, and manufacturing. Personnel shift scheduling is a complex 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, the current optimization algorithm aims at solving a planning version of the personnel scheduling problem. In this project, we propose to enhance its capabilities and to explore alternative algorithms for solving complex versions of the personnel scheduling problem, namely, rescheduling that requires revising planned schedules when unforeseen event occur, robust scheduling that takes into account demand variation and potential employee absenteeism, and multi-department/multi-site scheduling that considers possible employee transfers between departments or between sites. Our main objective is to develop an efficient algorithm for solving practical instances of each of these problem variants. To do so, we will perform mathematical modeling, data analysis, and methodological developments.