Research Of Optimization Algorithm For Nurse Scheduling Problem

Nurse scheduling problem is an NP hard problem in combinatorial optimization with multi-constraints.Given a collection of nurses,a collection of shifts and a set of constraints,nurse rostering consists in generating daily schedules for nurses by assigning a number of daily demanding shifts to nurses with different skills subject to predefined hard and soft constraints.A good nurse scheduling scheme can improve nurses' work efficiency and optimize the allocation of human resources in hospital and the algorithm can also be applied to other resource scheduling problems.The scheduling problem involves more constraints and the complexity of the problem is high.At present,most of the hospital nurse scheduling work is done by hand,which is time-consuming,and cannot get an efficient scheduling scheme.So,developing a scientific and efficient schedule in a reasonable time have become the urgent problem for hospitals.We do some studies about this issue in this paper.In recent years,researchers have proposed a wide variety of algorithms to solve the nurse scheduling problem,and adaptive neighborhood search algorithm is one of the best variable neighborhood search algorithm.ANS algorithm can get good solution for different use cases,but its drawback is that the calculation time is long.In order to overcome the shortcomings in calculation time of ANS algorithm,based on the single objective optimization model,a parallel and adaptive neighborhood search algorithm is proposed in this paper.The innovation of this algorithm is that(1)the design and implementation of a new initialization algorithm;(2)the improvement of the neighborhood search order of the ANS algorithm;(3)the parallel processing of the ANS algorithm.The results show that compared with the ANS algorithm,the improved PANS algorithm is better on the average value of the solution,and the operation time is shorter.The existing algorithms to solve the nurse scheduling problem are single point heuristic algorithm,namely,based on a single solution vector,the algorithm find the optimal solution in the solving process.The disadvantage of this type of algorithm is that the big number of iterations and the long solution time.Aiming at these defects,this paper proposes a new two steps optimization algorithm to solve the problem of nurse scheduling.In the first step of the optimization process,the genetic algorithm is used to obtain a local optimal solution set.In the second step of the optimization process,a kind of disturbance and restoration algorithms is designed to disturb the solutions.Then,nurses are reassigned to some shifts to jump out of local optimum and gain the global optimum.The experimental results show that the new two steps optimization algorithm can greatly reduce the solution time under the premise of sacrificing the accuracy of the solution.