A semi-cyclic shift patterns approach for nurse rostering problems

摘要

The paper, at hand, introduces a semi-cyclic shift patterns approach (SCSPA) that solves nurse rostering problem (NRP) at the Medical Centre, Universiti Kebangsaan Malaysia (UKMMC). Since night shift is the most problematic shift to assign due to the extra constraints that it has, the paper proposes a combination of semi-cyclic approach, which first allocates a predesigned night shift patterns cyclically, then allocates a combined morning and evening shift patterns in a non-cyclic manner until fulfilling the hard constraints. This is different from our previous work that adopted a non-cyclic shift pattern approach (NCSPA) to construct all of the possible valid shift patterns, which were a combination of morning, evening and night shifts which were incorporated to yield one-week shift patterns. Next, two shift patterns of one-week were allocated for each nurse until construct the initial roster. This paper presents a comparison between the proposed semi-cyclic approach and the previous non-cyclic approach. Beside the minimum violation penalty, we count the number of good patterns that each algorithm produces in order to measure the quality of constructed duty roster. Then, the approach applies simulated annealing algorithm in order to improve the overall produced roster as to enhance the initial roster that resulted from both algorithms. By using a semi-cyclic approach, two benefits over our previous work are gained, (i) the number of constructed shift patterns decreased remarkably, thus reduces the construction time; and (ii) allocating night shift patterns fairly for all nurses becomes more manageable. Based on the obtained results, the semi-cyclic approach yields a better duty roster as it produces more good patterns compared to our previous Non-cyclic approach.