Mon Tue Wed Thu Fri Sat Sun

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

1 *x x x d d d d* 2 *x x e e e x x* 3 *d d d x x e e* 4 *e e x x n n n* 5 *n n n n x x x*

## 2.3 Differentiability

At present, the differences of the (constraint and variable) violations upon a candidate local move are calculated na¨ıvely by first making the candidate move and then undoing it.

## 2.4 Incrementality

Local search proceeds from the current assignment by checking a number of neighbours of that assignment and picking a neighbour that ideally reduces the violation: the exact heuristics are often problem dependent. But in order to make local search computationally efficient, the violations of the constraint and its decision variables have to be computed in an incremental fashion whenever a decision variable changes value. As shown in Subsection 2.2, our initialisation Algorithm 1 can also be invoked with an arbitrary starting position s when decision variable Vsis assigned a new value.

We have implemented this algorithm in *Comet* [14], an object-oriented CP language with among others a CBLS back-end (available at **www.dynadec.com**).

## 3 Experiments

We now establish the practicality of the proposed violation maintenance algorithm by experimenting with it. All local search experiments were conducted under *Comet* (version 2.0 beta) on an Intel 2.4 GHz Linux machine with 512 MB memory while the constraint programming examples where implemented using SICStus Prolog.

Many industries and services need to function around the clock. Rotating schedules such as the one in Table 1 (a real-life example taken from [8]) are a popular way of guaranteeing a maximum of equity to the involved work teams (see [8]). In our first benchmark, there are day (d), evening (e), and night
(n) shifts of work, as well as days off (x). Each team works maximum one shift per day. The scheduling horizon has as many weeks as there are teams. In the first week, team i is assigned to the schedule in row i. For any next week, each team moves down to the next row, while the team on the last row moves up to the first row. Note how this gives almost full equity to the teams, except, for instance, that team 1 does not enjoy the six consecutive days off that the other teams have, but rather three consecutive days off at the beginning of week 1 and another three at the end of week 5. The daily workload may be uniform: for instance, in Table 1, each day has exactly one team on-duty for each work shift, and two teams entirely off-duty; we denote this as (1d,1e,1n,2x); assuming the work shifts average 8h, each employee will work 7 · 3 · 8 = 168h over the five-week-cycle, or 33.6h per week. Daily workload, whether uniform or not, can be enforced by global cardinality (gcc) constraints [13] on the columns. Further, any number of consecutive workdays must be between two and seven, and any change in work shift can only occur after