## 1 Introduction and Related Work  
### Introduction  
In this paper, the problem of nurse rostering is faced, which refers to the schedule of the personnel's shift in a hospital. This problem belongs to the wide category of timetabling problems. These problems deal with the allocation of resources to specific timeslots so that some specific constraints are satisfied and the created timetables/rosters are valid and effective. According to each case, the constraints, the sources and the elements defining the effectiveness of each timetable/roster are determined. These timetabling/rostering problems are non-deterministic polynomial time (NP)-complete in their general form [1], as far as their computational complexity is concerned, meaning that the difficulty to find a solution rises exponentially to their size and a deterministic algorithm, giving an acceptable solution in polynomial time, cannot be found [2, 3]. Therefore, alternative optimization methods, namely metaheuristics, have been developed in order to reach a (near) optimal solution for various kinds of the nurse rostering problem [4, 5]. Metaheuristics comprise a major class of approaches to solve the nurse rostering problem. They have been designed in order to cope with complex optimization problems in cases where other optimization methods have failed to be either effective or efficient. The main advantages of metaheuristic methods are their effectiveness and general applicability. In the literature, a lot of heuristic methods have been developed for dealing with the nurse rostering problem: genetic algorithms [6, 7, 8], tabu search [9, 10], simulated annealing [11, 12], variable neighborhood search [13, 14, 15], scatter search [16, 17], iterated local search [18, 19], particle swarm optimization [20], memetic algorithms [21], ant colony optimization [22], _etc_.  
The algorithm presented in this contribution comprises a heuristic method to solve the nurse rostering problem. More precisely, it is a stochastic variable neighborhood approach, which uses three different swap mechanisms, which are different from other swap mechanisms presented in the literature [13]. The use of these three swap operators by the proposed algorithm enables it to search in three different neighborhoods of the problem's search space. The reason why we decided to use a variable neighborhood search algorithm in order to solve this specific problem is that variable neighborhood search algorithms have been widely applied in many multi-objective optimization problems having very satisfactory results [23, 24, 25]. The innovation of the proposed algorithm is two-fold. First, although there are plenty of variable neighborhood algorithms applied to scheduling and timetabling problems in the literature [13, 26, 27, 28, 29], there is no two-phase stochastic variable neighborhood approach, to the best of our knowledge, applied to the nurse rostering problem. This was our main motivation in order to design and apply a two-phase stochastic variable neighborhood algorithm, so as to solve effectively and efficiently the nurse rostering problem. The second novelty of the proposed algorithm is the application of a \"stochastic moving segment grouping swap\" (see Subsection 3.2), which is innovative, to our knowledge, and different from other types of swaps presented in the literature [13, 26].  
Therefore, in this contribution, a new two-phase stochastic algorithm based on variable neighborhood search [30, 31] has been designed, developed and applied to the nurse rostering problem. The generic two-phase stochastic variable neighborhood algorithm proposed has been used in order to create feasible and efficient schedules of the personnel's shifts in many different hospitals having different types of constraints. In order to demonstrate the effectiveness, efficiency and genericapplicability of the proposed algorithm, its performance is compared with six other very effective algorithms published in the literature that have been applied to the same problem instances [32; 33; 34; 35; 36; 37].