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

在许多行业，特别是服务业，员工承担了大部分直接成本，并严重影响组织提供的产品和服务的质量。虽然有效利用劳动力是许多组织成功的关键因素，但构建高效的人员计划是一个非常复杂的问题：计划需要遵守许多通常复杂的合法性规则，例如每天允许的工作小时数，休息和休息时间的安排，以及工作周中不同轮班类型的允许模式。此外，规则和目标涉及考虑员工的偏好，如要求天数和公平问题。鉴于这种复杂性，即使是最先进的方法往往无法解决工业规模的人员调度问题（近）最优。此外，许多方法涉及复杂且难以实现的解决方案方法，例如分支和价格，其中规则处理深深嵌入解决方案算法中，使得难以使单个实现适应其他情况。此外，非常复杂的规则和成本结构无法使用某些建模和解决方案方法轻松表达：比如说，针对传统的混合整数线性规划模型难以描述活动序列合法性的问题，提出了一种基于状态流的混合整数线性规划模型来描述人员调度问题。扩大网络。这种方法的一个重要优点是，所得到的模型可以通过标准软件来求解。在该项目中解决的中心研究假设是，这种方法有可能形成一个新的有效的通用方法的基础上，适用于广泛的人员调度问题，并产生更好的结果比其他国家的最先进的方法。为了评估这一假设，本项目的具体目标是：（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.