Break Scheduling for Superivision Personnel

Shift Design and Break Scheduling

Benchmarks

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.

How are the benchmark instances generated?

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.

Example:

	hh:mm	minutes
shift duration	09:00	540
break time	01:40	.100	= floor[(540 – 20) / 50] x 10
lunch break	00:30	30
monitor break time	01:10	70

Created breaks	hh:mm
1 x lunch break	00:30
7 x monitor break	00:10

Example:

	hh:mm	minutes
shift duration	12:00	720
break time	03:00	180	= 720 / 4
lunch break	00:30	30
monitor break time	02:30	.150

Created breaks	hh:mm
1 x lunch break	00:30
6 x monitor break	00:20
3 x monitor break	00:10

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:

§ C₁ Break Positions

§ C₂ Lunch Breaks

§ C₃ Length of Work Periods

§ C₄ Minimum Break Times

§ C₅ Break Lengths

For that purpose, we formulate a simple temporal constraint satisfaction problem (STP) [1]. 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 [2]. So we finally obtain a shift, which contains the required breaktime and satisfies all the constraint C₁ Break Positions, C₂ Lunch Breaks, C₃ Length of Work Periods, C₄ Minimum Break Times and C₅ 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.

References

[1] Dechter, R., Meiri, I., and Pearl, J. (1991). Temporal constraint networks. Artif. Intell., 49(1-3):61–95.

[2] Papadimitriou, C. H. and Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall.

[3] 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.