Research On Variable Neighborhood Search Algorithm In Personnel Scheduling Problem

This paper intend to obtain a systematic and scientific plan for nurse scheduling problem while considering the skill differences among the nurses and their individual needs as well as the constraints from Labor laws, based on the known number of all nurses and the number of nurses required by different types of shift within a scheduling cycle, which optimizes human resource allocation of hospitals and reduces the pressure of the nurses effectively thus improves the efficiency and quality of nurses’work. The need of considering all the constraints makes the problem of nurse rostering so complicated that it has become an emergent and challenging problem for many hospitals to make an efficient nurse shift table for their daily management. In this paper, we will have some discussion about this issue.As an important heuristic, Variable Neighborhood Search Algorithm has been widely used in combinatorial optimization problems, which is also the kind of problem that nurse rostering belongs to. Based on the excellent optimization performance of Variable Neighborhood Search Algorithm, we designed the IVNS, an improved Variable Neighborhood Search Algorithm, to solve the discussed problem. The main innovation of this paper reflects in the stage of the perturbation, which involves:First, on the premise of not violating the hard constraints, IVNS randomly chooses even-number days and then exchanges the shifts between each two days of them. Experiments show that the performance of the solution to the perturbation strategy has little relevance to the number of nurses in the scheduling cycle and the best performance appears when choosing any two days to do this. The comparison experiment with the Hybrid Variable Neighborhood Search algorithm HVNS on a public test dataset shows that IVNS-D, which is based on the perturbation of shifts in different days, has a better performance.Second, on the premise of not violating the hard constraints, IVNS chooses one day randomly from the shift table and chooses even-number (which is less than the total number of the nurses) nurses randomly to have their shifts exchanged. Experiments show that the performance of the solution to the perturbation plan has great relevance to the total number of nurses in the scheduling cycle and that different nurses need to be chosen to do perturbation for the scheduling plan with different numbers of nurses. Under the same conditions, the IVNS-N which is based on the perturbation among different nurses has better performance compared to HVNS, while there being little difference when it is compared to IVNS-D.