Heuristic Algorithm Research On Nurse Rostering And The Design Of Rostering Management System

Nurse Rostering is a classic problem in staff scheduling, and it offen belongs to NP-complete problem. They have many features, such as restrictive, nonlinear and large scale, Traditional methods like linear programming and branch and bound cannot solve effectively in practice. So it usually utilizes heuristic algorithm to find a satisfied solution in acceptable time.Except for the personal requests, it also has other quite complex rules in the practice of nurse rostering. At present, existing rostering systems mainly focus on the informatization of the rostering work, with less consideration on the optimization. Based on this case, developing a rostering management system which can optimize the actual problem is necessary and meaningful.This paper research aims to design an intelligent rostering system which can schedule by independent choice, control the date attribute with its corresponding class and even add more functions. Through researching the solution of the initialization process in algorithm, the definition of neighborhood structure and perturbation methods to propose a proper algorithm, and then devise a practical nurse rostering system. The main contents of this paper are as follows:Ⅰ. In view of the nurse rostering, through the practical needs to define more scheduling rules and conclude the hard constraints and soft constraints. Because of the hard constraints in any case must be satisfied, as well as soft constraints are not necessary, so the definition of each soft constraint corresponding weight and presents the calculation formula of the penalty value, the problem is transformed into solving the objective function.Ⅱ. Researching the application of variable neighborhood search algorithm in scheduling to make some improvement in the algorithm:During initialization algorithm, adding modeling, considering dates attributes, multiple functions and personal affection in initial solution process to strengthen its feasibility; Next, optimize the different types of neighborhood structures so that the extended search space can be expanded in the process of variable neighborhood search, and the search time is not increased at the same time. The experiment indicates that the results of the algorithm are run on 55 standard cases,30 cases to reach the optimal solution.Ⅲ. Developed a scheduling system management which can generate and show scheduling table automatically, as well as support adjust the arrangements by hand. In system requirements analysis phase, described use case analysis, system architecture and module identification. In system design phase, mainly focus on designing of database table structures, system class and function modules. In the phase of system exploitation, adopt Spring MVC and Hibernate open-source framework based on MVC model.Applying the scheduling system automatically generates scheduling table, compared with the actual one under the same condition, reduce the violation of the constraint conditions and penalty value.