Article Preview
TopIntroduction
Transportation sectors, hospitals, companies, and academic institutions are a few examples of the bodies that have to run business within a framework of scheduling to ensure smooth transactions. In the hospital context, the Nurse Rostering Problem (NRP) is tackled by assigning qualified nurses to a set of different shifts over predefined scheduling period. The main merit of tackling NRP includes improving the hospital efficiency and allowing fair shift distribution among nurses subject to the satisfaction of hard and soft constraints. Hard constraints are those that should be satisfied, while violations of soft constraints are allowed but should be avoided, if possible. A roster is feasible if only it fulfills all the hard constraints, but the quality of the roster is determined by the level of the soft constraints satisfaction. However, it is almost impossible to find a roster that satisfies all constraints due to the fact that this problem is classified as a combinatorial optimization problem (Millar & Kiragu, 1998).
Researchers have been highly interested in the problem for the past five decades and several metaheuristic methods have been introduced to tackle different versions of NRP. These include Genetic Algorithm (Cai & Li, 2000; Tsai & Li, 2009), Ant Colony Optimization (Gutjahr & Rauner, 2007), Electromagnetic (Maenhout & Vanhoucke, 2007), Tabu Search (Burke, De Causmaecker, & Vanden Berghe, 1999; Dowsland, 1998), Simulated Annealing (Brusco & Jacobs, 1995), Variable Neighbourhood Search (Bilgin, De Causmaecker, Rossie, & Vanden Berghe, 2011; Burke, Curtois, Post, Qu, & Veltman, 2008), and Scatter Search (Burke, Curtois, Qu, & Berghe, 2009). For more details see the surveys of Burke, De Causmaecker, Berghe, and Van Landeghem, (2004), and Cheang, Li, Lim, and Rodrigues (2003).
Burke et al. (1999) hybridized the tabu search with a greedy shuffling move to solve NRP. The hybrid tabu search was tested using real dataset sampled from Belgian hospitals. The proposed method was better than the manual methods in terms of solution quality and computational time. Burke et al. (2001) hybridized the tabu search optimizer with genetic algorithm for NRP. The performance of the hybrid algorithm was compared against tabu search using real dataset sampled from Belgian hospitals. In comparison, the hybrid genetic algorithm provided the best results. In another study, Bellanti et al. (2004) separately applied two methods including tabu search and iterated local search for NRP. The performance of their methods was measured using real dataset from an intensive care unit of a hospital in Turin, Italy. Özcan (2005) hybridized the hill climbing optimizer within the genetic algorithm to tackle NRP. The author obtained satisfactory results using real dataset from the Memorial Hospital, Turkey.
Gutjahr and Rauner (2007) investigated the applicability of ant colony optimization for NRP using dataset from Vienna Hospital, Austria. The ant colony optimization obtained high quality solutions in a reasonable computational time in comparison with simulated annealing method. Burke et al. (2008) hybridized the variable neighbourhood search with heuristic ordering technique to tackle NRP. The results of hybrid algorithm outperformed commercial genetic algorithm software applied over 40 hospitals in Belgium. An efficient genetic algorithm was presented by Tsai and Li (2009) for NRP. Their method obtained suitable results when tested using a dataset from the Otolaryngology Hospital in Taiwan. Burke et al. (2009) hybridized the scatter search with hill climbing to solve NRP. The performance of the hybrid method is evaluated on real-world benchmark dataset, called 'BCV,' sampled from Belgian hospitals. Their method is compared with the previous methods using 'BCV.' They concluded that their hybrid method is robust and effective on a wide range of real-world dataset.