Fast optimization algorithms for complex personnel scheduling problems

Kronos加拿大系统公司将劳动力调度软件商业化，服务于全球1100多家组织，其中包括加拿大的100多家组织。该软件允许确定不同领域的员工轮班时间表，包括零售、医疗保健、休闲和酒店以及制造业。人员轮班调度是一个复杂的组合优化问题，它涉及确定每个可用员工的工作日，每个工作日的确切班次，以及每个班次要执行的工作，以便最好地满足员工对每个工作的需求。在Kronos，这个问题是通过一个基于数学编程的优化算法来解决的，这个算法的核心策略是多年前开发的。为了使算法对最近集成的复杂特征具有更强的鲁棒性，我们在本项目中提出了新的核心策略，即一种新的分解算法将问题分解为子问题，改进求解每个子问题的算法，以及一种新的移位枚举算法。我们的主要目标是构思一种高效且稳健的算法，能够解决Kronos客户遇到的实际问题实例。为了实现这一目标，我们将进行数学建模、数据分析和方法开发，其中包括整数规划、局部搜索、大邻域搜索和机器学习等。这项研究的成功结果将被集成到Workforce Scheduler软件中。考虑到所提出的开发将是该软件的核心，它们将为Kronos提供商业优势，使其能够提供能够解决大型复杂人员调度问题的改进软件。因此，加拿大公司将直接受益于该项目的积极影响。此外，大量已经使用Workforce Scheduler的加拿大公司/组织也将间接受益于该项目，因为他们将获得新软件版本的访问。最后，该项目将资助7名硕士、博士和博士后的培养。

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.