Harmony Search with Greedy Shuffle for Nurse Rostering

Harmony Search with Greedy Shuffle for Nurse Rostering

Mohammed A. Awadallah (Universiti Sains Malaysia, Malaysia), Ahamad Tajudin Khader (Universiti Sains Malaysia, Malaysia), Mohammed Azmi Al-Betar (Universiti Sains Malaysia, Malaysia, & Jadara University, Jordan) and Asaju La’aro Bolaji (Universiti Sains Malaysia, Malaysia)
Copyright: © 2012 |Pages: 21
DOI: 10.4018/jncr.2012040102


In this paper, a hybridization of Harmony Search Algorithm (HSA) with a greedy shuffle move is proposed for Nurse Rostering Problem (NRP). NRP is a combinatorial optimization problem that is tackled by assigning a set of nurses with different skills and contracts to different types of shifts, over a pre-determined scheduling period. HSA is a population-based method which mimics the improvisation process that has been successfully applied for a wide range of optimization problems. The performance of HSA is enhanced by hybridizing it with a greedy shuffle move. The proposed method is evaluated using a dataset defined in first International Nurse Rostering Competition (INRC2010). The hybrid HSA obtained the best results of the comparative methods in four datasets.
Article Preview


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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2019): 2 Released, 2 Forthcoming
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing