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:

 

§         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) [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 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.

 

 

 

 

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.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2008 ©  Database and Artificial Intelligence Group, Vienna University of Technology