Generic and Efficient Personnel Scheduling Approaches Based on State-Expanded Network Formulations
Final Report Abstract
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. Making effective use of the workforce by devising high-quality personnel schedules is thus a critical success factor. Despite considerable advances in the recent years, however, modelling and solving large and complex personnel scheduling problems remains an important challenge. A promising approach to address this challenge is to formulate personnel scheduling problems as MILP models on the basis of flows in state-expanded networks. An advantage of this approach is that it is capable of efficiently handling problems with complex scheduling rules without relying on complicated and hard-to-implement solution approaches such as Branch-and-Price. In this project, we developed a generic approach for generating state-expanded networks based on formulating the generation of a feasible schedule as a Dynamic Programming Model involving rule-related states and state transitions representing assignments to pieces of work. Since the state transition function and the evaluation of the feasibility of a state can be performed by any procedure, this approach is very flexible and capable of handling even very complex rules. One of the challenges of state-expanded network models is that for large and complex personnel scheduling problems, the network can become very large rendering the whole approach impractical and/or not competitive to other state-of-the-art approaches. To address this issue, we developed both exact and heuristic approaches for reducing the size of stateexpanded network models in this project. The exact approaches exploit the hierarchical structure of personnel scheduling problems: Instead of creating on large state-expanded network for the full problem on the highest level of detail, we propose to create multiple stateexpanded networks operating on different levels of detail and to link them in the mathematical optimization model. We show that using this idea can considerably reduce the size of the resulting model instances as well as the time needed to solve these instances. As an example, based these ideas and combined with a novel set of aggregate constraints enforcing the correct sequencing of activities, we were able to design a new state-of-the-art approach for Multi-Activity Shift Scheduling Problems that was able to close several previously open instances in less than 30 minutes on a notebook computer. In addition, we designed a machine learning approach for heuristically reducing the size of state-expanded networks. This approach, which uses the information associated with nodes and arcs in the network as well as instance information, achieves state-of-the art performance for heuristically solving personnel scheduling problems such as Multi-Activity Shift Scheduling problems. Finally, one of the goals of the project was to investigate the relations of state-expanded networks to related graph-based approaches such as Decision Diagrams (DDs). This investigation developed differently than planned and led to a set of contributions to the emerging field of DDs: A local search framework for compiling relaxed DDs, a set of consistency conditions for relaxed DDs and a new Primal-Dual Algorithm for Combinatorial Optimization that only relies on Decision Diagrams.
Publications
- A Local Search Framework for Compiling Relaxed Decision Diagrams. In: van Hoeve WJ. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2018. Lecture Notes in Computer Science, vol 10848. Springer, Cham
Römer M., Cire A.A., Rousseau LM.
(See online at https://doi.org/10.1007/978-3-319-93031-2_36)
