Hybridization of heuristic approach with variable neighborhood descent search to solve nurse Rostering problem at Universiti Kebangsaan Malaysia Medical Centre (UKMMC)

摘要

Nurse Rostering problem (NRP) represents a subclass of scheduling problems that are difficult to solve for optimality. It deals with assigning shifts to staff nurses subject to satisfying required workload and other constraints. The constraints are classified into hard constraints (compulsory) and soft constraints (should be satisfied as much as possible). A feasible solution is a solution that satisfies all hard constraints. However, the quality of the duty roster is measured based on satisfying the soft constraints. This study is an attempt to solve a real world scenario from Universiti Kebangsaan Malaysia Medical Center (UKMMC). Currently, the duty roster is constructed manually by head nurses in different wards. So, the main goal of our work is to generate good duty roster that satisfied all the hard constraints which are required by (UKMMC). A constructive heuristic is introduced to solve (UKMMC) nurse rostering problem. This heuristic is a hybridization of cycling schedule with non-cycling schedule (random order). If the solution is not feasible, we apply a repairing mechanism to produce feasible solution. Then, the initial solution is improved by applying variable neighborhood descent search. Computational results are presented to demonstrate the effectiveness of the proposed approach.