Abstract
Nurse Rostering Problem (NRP) is a well-known NP-Hard combinatorial optimization problem. The fact is that coping real-world constraints in allocating the shift duties fairly among the available nurses is still a hard task to accomplish. The problem becomes more serious due to the shortage of nurses. Thus, this work aims to tackle this problem by hybridizing an Enhanced Harmony Search Algorithm (EHSA) with the standard Hill climbing (HC). This hybridization may help to strike the balance between exploration and exploitation in the searching process. The proposed algorithm is called Climbing Harmony Search Algorithm (CHSA) where it applied to solve a real-world NRP dataset, which arises at the Medical Center of Universiti Kebangsaan. The results show that CHSA performs much better than EHSA alone and Basic Harmony Search algorithm (BHSA) in all instances in terms of obtained penalty values (PVs), desirable patterns (DPs) and computational time as well.