Generic and Efficient Personnel Scheduling Approaches Based on State-Expanded Network Formulations

在许多行业，特别是在服务行业，员工承担了直接成本的主要部分，并严重影响了组织提供的产品和服务的质量。虽然有效利用劳动力是许多组织成功的关键因素，但构建有效的人事安排是一个非常复杂的问题：时间表需要遵守许多通常错综复杂的法律规则，例如，每天允许的工作时间，休息和休息时间的安排，以及工作周中不同班次类型的允许模式。此外，规则和目标还涉及到考虑员工的偏好，例如要求休假和公平问题。考虑到这种复杂性，即使是最先进的方法通常也无法将工业规模的人员调度问题解决到（接近）最优。此外，许多方法涉及复杂且难以实现的解决方案方法，例如branch-and-price，其中规则处理深深地嵌入到解决方案算法中，使得难以将单个实现调整到其他情况。此外，非常复杂的规则和成本结构不能轻易地用某些建模和解决方法来表达：例如，控制活动序列合法性的模式规则通常难以在经典的混合整数线性规划公式中建模。解决上述挑战的一个有希望的新方法是将人员调度问题制定为基于状态扩展网络流的混合整数线性规划模型。这种方法的一个重要优点是，得到的模型可以用标准软件求解。本项目的中心研究假设是，这种方法有可能形成一种新的、有效的通用方法的基础，适用于广泛的人事调度问题，并产生比其他最先进的方法更好的结果。为了评估这一假设，本项目的具体目标是：(i)研究和开发基于状态扩展网络模型中表达各种人员调度问题变体和处理复杂调度规则的通用方法；（ii）通过利用人员调度问题的分层结构和减小网络规模来改进状态扩展网络的公式；（iii）开发通用和有效的启发式方法，利用允许处理大规模实例的模型结构；（iv）探索基于分解的解决方案，利用状态扩展网络公式的结构。

In many industries, particularly in the service sector, employees incur a major part of the direct costs and heavily impact the quality of the products and services delivered by an organization. While making effective use of the workforce is thus a critical success factor for many organizations, constructing efficient personnel schedules is a very complex problem: The schedules need to comply with a multitude of often intricate legality rules governing, for example, the number of allowed work hours per day, the placement of breaks and rest periods, and the allowed patterns of different shift types in a work week. Moreover, the rules and objectives involve the consideration of employee preferences such as requests for days of and fairness issues. Given this complexity, even state-of-the-art approaches are often unable to solve industrial-scale personnel scheduling problems to (near-)optimality. In addition, many approaches involve complex and difficult-to-implement solution approaches such as branch-and-price in which rule handling is deeply embedded in the solution algorithm making it hard to adapt a single implementation to other cases. Furthermore, very complex rules and cost structures cannot easily be expressed using certain modeling and solution approaches: For example, pattern rules governing the legality of activity sequences are typically difficult to model in classical mixed-integer linear programming formulations.A promising new approach to address the described challenges is to formulate personnel scheduling problems as mixed-integer linear programming models on the basis of flows in state-expanded networks. An important advantage of this approach is that the resulting models can be solved by standard software. The central research hypothesis addressed in the project is that this approach has the potential to form the basis of a novel efficient generic approach applicable to a broad range of personnel scheduling problems and yielding better results than other state-of-the art approaches. In order to evaluate this hypothesis, the specific objectives of this project are (i) to investigate and develop generic approaches for expressing various personnel scheduling problem variants and for handling complex scheduling rules in models based on state-expanded networks, (ii) to improve the state-expanded network formulations by exploiting hierarchical structure of personnel scheduling problems and reducing network size, (iii) to develop generic and efficient heuristic approaches exploiting the model structure allowing to handle large-scale instances and (iv) to explore decomposition-based solution approaches exploiting the structure of the state-expanded network formulations.