## 1 Introduction and Related Work
### Related Work  
[PERSON] and [PERSON] presented in [32] a hybrid methodology that utilizes the strengths of operations research and artificial intelligence. In particular, an approximate integer linear programming model is firstly solved, and its solution is further improved using local search techniques. Furthermore, a tabu search strategy is applied in order to construct effective and efficient solutions. [PERSON] _et al._, present a hybrid artificial intelligence approach for a class of over-constrained nurse rostering problems, [33] which comes in two phases. The first phase solves a relaxed version of the problem, which only includes hard rules and part of the nurses' requirements for shifts. In the second phase, adjustments with descend local search and tabu search are applied to improve the solution. The algorithm presented in [34] is a shift sequence-based approach that consists also of two stages: (a) Constructing high quality sequences for nurses by only considering the sequence constraints and (b) Iteratively constructing schedules for nurses and the overall rosters, based on the sequences built and considering the schedule and roster constraints. Greedy local search carried out during and after the roster construction manages to improve the (partial) rosters built. [PERSON] _et al._, present a genetic algorithm approach to solve the medical doctor rostering problem in a hospital emergency department in [35]. More specifically, they intend to automate the creation of timetables by applying genetic algorithms in an actual hospital emergency department. Firstly, a heuristic-schedule builder, designed _ad hoc_ to satisfy the hard constraints, produces an initial population of feasible solutions. Afterwards, iteratively, a genetic algorithm obtains new generations of feasible individuals, thanks to the use of a specific crossover operator, based on the exchange of whole workweeks that operates together with a repair function. [PERSON] and [PERSON] describe in [36] a single-phase goal-programming algorithm for scheduling nurses in one unit of a hospital. The goals represent the scheduling policies of the hospital and nurses' preferences for weekends on and off. Experiments on one unit with 11 nurses resulted in satisfactory results. Finally, in [37], [PERSON] _et al._, present the efficiency of constraint programming for solving the nurse rostering problem. Experimental results obtained are very satisfactory regarding response time and flexibility of the approach. The proposed variable neighborhood search algorithm uses the same formalism for modeling the nurse rostering problem, tries to minimize the same fitness function and uses the same performance criteria in order to evaluate the quality of resulted rosters, as the ones used in [32; 33; 34; 35; 36; 37]. Therefore, a straightforward comparison of their experimental results is fair. Moreover, in order to have a fair comparison with these algorithms, we decided to use the exact same input instances used by these six approaches. Computational results showed that the proposed two-phase variable neighborhood search algorithm achieves better results compared to these six very effective algorithms. The comparison was carried out on the basis of seven instances taken from real world situations that were also used as input by the six published effective approaches mentioned above. In one case, the proposed algorithm manages to beat the best-known fitness achieved till now. In addition, in the rest of the six cases, the proposed algorithm manages to reach, for each different instance, the best-known fitness achieved in the literature and demonstrates, experimentally, that in these instances, there is more than one roster that achieves the best-known fitness. This paper is organized as follows. Section 2 defines the nurse rostering problem and the constraints used, in most cases, in order to evaluate the resulting shift schedules. Section 3 describes the proposed two-phase variable neighborhood algorithm, while Section 4 describes the input data used.