
| Table 3: Evaluation of variable selection heuristics   |              |          |     |
|--------------------------------------------------------|--------------|----------|-----|
| No. of choice points                                   | No. of fails | CPU(sec) |     |
| MinSizeInt                                             | 8966         | 7995     | 1.3 |
| MaxSizeInt                                             | 10706        | 9723     | 1.5 |
| MinMinInt                                              | 10703        | 9720     | 1.5 |
| MaxMinInt                                              | 11978        | 10995    | 1.8 |
| MinMaxInt                                              | 9290         | 8319     | 1.2 |
| MaxMaxInt                                              | 12603        | 11620    | 1.8 |

| Table 4: Result of fixed length sliding window as the fragment over iterations in the LNS approach Length Initial solution Iter 1 Iter 2 Iter 3 Iter 4 CPU(sec) 4 49 38 33 32 31 1.56 7 49 32 31 24 22 1.78 14 49 31 16 10 8 1.80   |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|

- MinMaxInt: chooses the variable with the least maximal bound
- MaxMaxInt: chooses the variable with the greatest maximal bound Within the same constraint programming model for the problem, we compare in Table 3 these variable selection heuristics with respect to the number of choice points during the tree search and the number of fails encountered. Among the 6 heuristics tested, we can see that the MinSizeInt and MinMaxInt heuristics perform better than others but no statistically significant differences between themselves can be identified. We just use MinSizeInt in the follow re-optimization procedures within the LNS approach.

## 4.2 Comparison Of The Three Fragment Selection Strategies

The first fixed sliding window strategy chooses the fragment of variables, represented as row*column, to be relaxed and re-optimized. The size of row is the total number of nurses while the size of column is 7 and 14 (weekly length). We also set a small size of 4 as the column size for testing purposes. The best improved rule is used on this problem. Table 4 presents the cost of solutions over iterations, from which we can see that choosing large length of sliding window obtains better result as there is more chance to obtain improved solutions within a larger neighboring size of the solution space. Meanwhile the searching time spent is acceptable for this problem.

To evaluate strategy 2 concerning a variable sliding window with overlap, different lengths of the column are compared. Due to the weekly related constraints in the problems, we set the basic length of the column as 7 (days). Based on this, we also tested different lengths of 11, 13 and 15 days. The results presented in Fig 4 demonstrate that with the largest length of sliding window = 15, better improved solutions can be obtained within less number of iterations.

We test strategy 3 based on the constraint and propagation directed fragment, and compare it with the above two strategies in Fig 5. Results demonstrate that strategies 2 and 3 perform similarly, both better than strategy 1. LNS with strategy 2 and strategy 3 obtained intervening objective values over iterations, partially because the length of columns in strategy 2 is similar to that of strategy 3, but the size of rows