TL;DR
This paper introduces two novel methods for solving the complex Rotating Workforce Scheduling (RWS) problem by leveraging Satisfiability Modulo Theories (SMT). By formulating RWS constraints using linear integer arithmetic and, more effectively, bitvectors, the authors demonstrate a significant improvement in the number of solvable instances compared to existing exact methods.
What Problem Does This Paper Address?
Many businesses, from hospitals to police stations, require 24/7 staffing. Rotating Workforce Scheduling (RWS) is a crucial real-world problem that involves assigning shifts to employees over a period (typically a week) in a cyclic manner, ensuring all necessary temporal requirements and other constraints are met. While various approaches exist, including integer programming, network flow, constraint programming, and heuristics, solving large-scale RWS instances remains a significant challenge. This paper aims to address this by exploring the power of SMT solvers, which combine the expressiveness of first-order logic with efficient SAT-solving capabilities, to find more effective and efficient solutions.
Methods
The authors propose two distinct modeling techniques for RWS using SMT:
- Linear Integer Arithmetic (LIA): This approach models RWS using variables representing shifts for each employee and day. Shifts are mapped to integers, and temporal requirements are expressed using linear arithmetic constraints. This method provides an elegant formulation but can struggle with a large number of employees.
- Bitvector Theory: This more advanced technique represents the schedule using bitvectors. Each bitvector can represent a shift across all employees and days, or individual shifts for a single employee. This allows for compact representations and leverages bitwise operations (AND, OR, XOR) and bit-level arithmetic. Novel algorithms are presented for handling constraints like shift block length (minimum and maximum consecutive shifts) and illegal shift sequences using bit manipulation and bit counting (Hamming Weight). This approach is shown to be more effective for larger problems.
Datasets
The authors evaluated their approaches on 20 benchmark instances. The first three problems are standard benchmarks used in most RWS literature, and the remaining 17 were derived from real-world workforce scheduling scenarios. These instances vary in size, with the largest having 163 employees and 4 shifts (including day-off), leading to a search space of 4^163 * 7.
Key Insights and Ideas
- SMT as a Powerful Tool for RWS: The paper demonstrates that SMT solvers, particularly when combined with clever encoding techniques, can effectively tackle complex combinatorial problems like RWS, outperforming traditional methods in terms of the number of solvable instances.
- Bitvectors Offer Superior Compactness and Efficiency: The bitvector encoding proved to be significantly more efficient than the linear integer arithmetic approach. This is attributed to the ability of bitvectors to represent constraints more compactly and leverage specialized bitwise operations, leading to reduced variable counts and faster solver performance.
- Novel Bitvector Algorithms for Constraints: The development of specific algorithms for handling shift block lengths (minimum and maximum) and illegal shift sequences using bit manipulation (like Hamming Weight calculation and bitwise shifts) is a key contribution. These algorithms are designed to be declarative and suitable for SMT solvers.
- Cyclicity Handling: The paper addresses the challenge of cyclic schedules by proposing methods to ensure that the last day of a week is adjacent to the first day of the next, and the last day of the entire planning period is adjacent to the first.
Key Results
- The proposed SMT-based approaches, particularly the bitvector encoding, significantly outperform other exact methods in terms of the number of instances solved.
- The bitvector approach allowed solvers like MathSAT and Boolector to solve 18 out of 20 instances, a notable improvement over the LIA approach where the best solver (Z3) solved 15 instances.
- Figure 1, comparing the fastest solvers for each approach (Z3 for LIA, MathSAT for bitvectors), shows that the bitvector approach achieves significantly faster solving times across all instances.
- Compared to other exact methods like FCS and CP-Rota, the SMT approach solved 5 more instances than FCS and outperformed CP-Rota on most instances, though CP-Rota was better on one specific instance (instance 7).
Limitations and Future Work
- Hardware Dependency: The authors acknowledge that direct comparison of runtimes is limited due to different hardware specifications used in previous studies.
- Instance 7 Anomaly: The paper notes that SMT solvers struggled with instance 7, which was efficiently solved by other exact methods. The reason for this anomaly is not fully understood and warrants further investigation.
- Future Work: The paper suggests that further exploration of SMT-based approaches for RWS and related scheduling problems is promising. The success of the bitvector encoding indicates that exploring more advanced bit-level operations and potentially specialized SMT theories could lead to even greater performance improvements.
Summary updated