Primitive constraints are used to model the problem. For example, one extra constraint to the above list is that "after a Late shift no Early shift is allowed". It can be expressed by using "if si j = *Late*, then si j 6= *Early*".

In addition to primitive constraints, to efficiently model the features of the problem, global constraint such as cardinality(gcc) has been used in the model. For example, the demand coverage constraint can be expressed as *cardinality*(x,D,LB,UB), restricting the decision variable x to take only values in shift type set D of a number of times within the bounds [LB,UB]. It is quite straightforward to use gcc to model the constraint crisply, i.e. the constraint is either satisfied or not satisfied [12, 20]. However, the problem we are trying to tackle is over-constrained. Using only crisp constraints to model all the above stated constraints does not usually produce feasible solutions for the problems. Therefore, global soft constraints have been used to model the originally over-constrained problems as constraint optimization problems. Global soft constraints upon group of variables can be seen as a preferential constraint whose satisfaction is not required but preferred. A cost is associated to each global soft constraint in order to quantify the violation of the corresponding constraint. The objective is defined as to minimize the total sum of the cost.

Definition: µ is a violation measure for the global constraint c(x1,···, xn) iff µ is a function D1 ×
D2*×···×*Dn ⇒ R
+. s.t. ∀A ∈ D1×D2*×···×*Dn, where D1,···,Dn is the domain of x1,···, xn. µ(A) = 0 iff tuple A satisfies c(x1,···, xn).

To evaluate the violation of the soft constraint, we define the violation measure µ for soft constraint cardinality as:

$\mu(soft-cardinality)=card-UB,\quad if\quad card>UB$  $=LB-card,\quad if\quad card<LB$
$$(1)$$
For example, due to the constraint that nurse i should work 4-5 Day shifts in one week, assigning the nurse Day shifts of less or over the range [4, 5] will cause a penalty of 100. For a given schedule: l =
Day, Day, Day, Off, Off, Off, Off, we have *Cost*(l) = w× µ(l) = 100×(4−3) = 100, where *card*(l) =
3,LB = 4,UB = 5.

In this paper we use the global constraint gcc and its soft version at different stages of our solution procedure. In the first stage, only hard constraints are considered and they are modeled as crisp constraints to obtain initial solutions. In the second stage, local search is applied to improve the initial solution with respect to global soft constraints. The soft gcc is used not only in the objective function, but also to decide the structure of neighborhood in the LNS approach. That is, we choose variables to be added to the fragment if these variables are linked and propagated by these soft global constraints.

## 3 The Constraint-Directed Large Neighborhood Search Approach

LNS is firstly proposed by Shaw in [17] to solve the vehicle routing problem. The framework of LNS is a very simple scheme in the context of constraint programming. The basic idea is to iteratively relax and then re-optimize a part of the solution assignment to find better solutions over iterations. Constraint programming is used to generate the new assignment for the relaxed part of variables and to add bound to the search to ensure that the new solution found is better than the current one.

Table 1 presents our 2-stage approach to solve NRPs. In the first stage, a feasible initial solution is constructed with respect to the hard constraints. In the second stage, LNS is used to iteratively improve