different subsets of the constraints. Constraints are usually categorised into two groups: hard constraints, which must be satisfied to get feasible solutions for use in practice, and soft constraints, which are not obligatory but are desired to be satisfied as much as possible. A common hard constraint is to assign all shifts required to the limited number of nurses, i.e. demand coverage. The violations of soft constraints are usually used to evaluate the quality of solutions, for example, if a balanced workload is allocated so that human resources are used efficiently. Examples of constraints we concern in this work are listed as follows:
The hard constraints are:
- To a full-time nurse, 18 shifts per scheduling period have to be assigned.

- To a part-time nurse, 10 shifts per scheduling period have to be assigned.

- On each day there starts at most one shift for a nurse.

- Each nurse receives at most 4 night shifts, of which at most 3 on consecutive days, per scheduling period.

- Each nurse works at most 6 days in a row.

- Each any 3 consecutive weekends, at least one is free of labor. - After a series of 1, 2, or 3 night shifts, there is 48 hours free of labor.
The soft constraints for a nurse are:
- A single night shift causes a penalty of 100.

- A stand-alone shift, i.e. a single shift with day off before and after, causes a penalty of 100. - A weekend with 1 shift causes a penalty of 100. - A single day off causes a penalty of 10.

- A full-time nurse receives 4 or 5 shifts, and a part-time nurse receives 2 or 3 shifts per week (from Monday till Monday). A penalty of 1, 4, 9 and 16 occurs for a deviation of 1, 2, 3 and 4 from this range, respectively.

- A full-time nurse can work a series of shifts of length 4 to 6, and a part-time nurse can work a series of shifts of length 2 or 3. A penalty of 1, 4 and 9 occurs for a deviation of 1, 2 and 3, respectively.

(Too short series at the end of the scheduling period are not penalized as they are carried forward to the next scheduling period).

## 2.2 Constraint Programming Model For The Nurse Rostering Problem

Following our previous research [20], we formulate the NRPs in a constraint programming model within the LNS scheme.

Denotations:
- I: set of nurses available(index i)

- J: number of days within the scheduling period(index j)
- K: set of shift types(includes off shift)(index k)
- Djk:coverage demand of shift type k on day j
- Decision variable si j: the shift type assigned to nurse i on day j