An evolutionary algorithm based on constraint set partitioning for nurse rostering problems

摘要

The nurse rostering problem (NRP) is a representative of NP-hard combinatorial optimization problems. The hardness of NRP is mainly due to its multiple complex constraints. Several approaches, which are based on an evolutionary algorithm (EA) framework and integrated with a penalty-function technique, were proposed in the literature to handle the constraints found in NRP. However, these approaches are not very efficient in dealing with large-scale NPR instances and thus need to be improved upon. In this paper, we investigate a large-scale NRP in a real-world setting, i.e., Chinese NRP (CNRP), which requires us to arrange many nurses (up to 30) across a 1-month scheduling period. The CNRP poses various constraints that lead to a large solution space with multiple isolated areas of infeasible solutions. We propose a single-individual EA for the CNRP. The novelty of the proposed approach is threefold: (1) using a constraint separation to partition the constraints into hard and soft constraints; (2) using a revised integer programming to generate a high-quality initial individual (solution), which then leads the subsequent EA search to a promising feasible solution space; and (3) using an efficient mutation operator to quickly search for a better solution in the restricted feasible solution space. The experimental results based on extensive simulations indicate that our proposed approach significantly outperforms several existing representative algorithms, in terms of solution quality within the same calculation times of the objective function.