A Constraint Programming Application for Rotating Workforce Scheduling - Developing Concepts in Applied Intelligence - page 86

6 Labeling and Allocation Strategies

The default strategy in CP-Rota is to first label the (reified) work/“day-off”
Boolean variables. Then, all original variables of the schedule are labeled with
the “first-fail” option. We call this strategy

S 1 .When S 1 did not yield a solution

S 2 , which is to label all schedule variables
from left to right, trying their values from lowest to highest. If this does not
yield a solution within 1000 seconds,

within 1000 seconds, we used Strategy

S 3 is used: Reified constraints are used
to compute, for each column, the number of still missing shifts of each type.
Processing the columns in order, we then choose the shift type that misses the
least number of elements in that column, and assign it to a feasible variable with
smallest domain. When

S 3 also fails to find a solution within 1000 seconds, S 4

is used: It is similar to S 3 , except the columns are not processed from left to

right, but in descending order of their number of still missing shifts of any type.

Table 1. Comparison between FCS and CP-Rota .

Ex. n FCS (time in sec) CP-Rota (sec) Strategy

1 9 0.9 0.02 S 1

2 9 0.4 0.02 S 1

3 17 1.9 0.24 S 1

S 1

4 13 1.7 0.03

5 11 3.5 0.98 S 1

6 7 2 0.02 S 1

7 29 16.1 0.07 S 2

8 16 124 964 S 1

9 47 > 1000s 19 SWI, S 4

10 27 9.5 > 1000s -

11 30 367 > 1000s -

12 20 > 1000s > 1000 -

13 24 > 1000s 114 S 1

14 13 0.54 940 S 1

> 1000s > 1000s

15 64 -

16 29 2.44 216 S 1

17 33 > 1000s 18 SWI, S 3

18 53 2.57 > 1000s -

19 120 > 1000s > 1000s -

20 163 > 1000s > 1000s -