Shift Design and Break Scheduling
Benchmark instances for the shift design and break scheduling problem
Validator, benchmark instances and best known solutions for the shift design and break scheduling problem can be found here.
Benchmark instances for the supervision personnel break scheduling problem.
We propose two different sets of randomly generated examples for the regarded break scheduling problem for supervision personnel, which can be used further by other researchers to compare their results with ours.
Set 1 of randomly generated problems (download)
These examples were generated from the first thirty benchmark instances in set 1 for the shift-design problem.
Set 2 of randomly generated problems (download)
These examples were generated from the first thirty benchmark instances in set 2 for the shift-design problem.
Problem settings for the benchmark instances
The settings for these instances were obtained from a real-life use case for supervision personnel. The following screenshot summarizes how much break time should be scheduled in each shifts and presents the constraint-settings for a desired solution.
1. Generating a shift plan.
To generate a shift plan we considered the randomly generated benchmark instances for the shift design problem. The shifts are extracted from the sample solution of each instance and represent the input shift plan for an instance of the break scheduling problem for supervision personnel.
2. Creating the breaks of each shift.
First of all, for each shift the total amount of break time to be scheduled is computed. The break time is then distributed among the lunch breaks of required length and monitor breaks whose durations range between ten or twenty minutes.
3. Scheduling breaks in each shift.
Breaks are scheduled within their associated shifts such that the following constraints satisfy the following constraints of the break scheduling problem for supervision personnel are satisfied completely:
§ C1 Break Positions
§ C2 Lunch Breaks
§ C3 Length of Work Periods
§ C4 Minimum Break Times
§ C5 Break Lengths
For that purpose, we formulate a simple temporal constraint satisfaction problem (STP) . In our formulation the start and end of shifts and breaks are modelled as variables. The values for minimum and maximum distances and lengths are encoded as time intervals restricting the relative distances between variables. The resulting STP is the solved with a randomized version of Floyd-Warshall’s all-pairs-shortest-path algorithm . So we finally obtain a shift, which contains the required breaktime and satisfies all the constraint C1 Break Positions, C2 Lunch Breaks, C3 Length of Work Periods, C4 Minimum Break Times and C5 Break Lengths.
5. Determining staffing requirements.
Finally, for each time slot of the planning period the staffing requirements is set to the number of working employees. In that way we can guarantee that the resulting problem instance has a solution, which avoids shortage and excess of employees. Moreover, that solution is able to satisfy all other constraints.
 Dechter, R., Meiri, I., and Pearl, J. (1991). Temporal constraint networks. Artif. Intell., 49(1-3):61–95.
 Papadimitriou, C. H. and Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall.
 Andreas Beer, Johannes Gärtner, Nysret Musliu, Werner Schafhauser, Wolfgang Slany. An AI-Based Break-Scheduling System for Supervisory Personnel. Accepted for publication in IEEE Intelligent Systems.
Solutions for this problem from other researchers
Solutions from Akkermans et al: Solutions
Reference: Arjan Akkermans, Gerhard Post and Marc Uetz, Solving the Shifts and Breaks Design Problem Using Integer Linear Programming p. 137-152 at Proceedings of PATAT 2018 (http://patatconference.org/patat2018/proceedings/)