中文摘要：

护士排班问题（nurse rostering problem,NRP）是多约束条件下的NP难优化问题,目前大多数算法难以在计算时间和求解质量之间达到较好的平衡。针对此难题,提出一种基于整数规划（integer programming,IP）与演化优化（evolutionary optimization algorithm,EA）混合的一种算法机制,分两步对护士排班问题进行求解。第一步采用IP算法求解简化后的NRP,得到一个高质量的初始解;第二步则在初始解的基础上采用演化算法进一步优化而得到更优的结果。实验结果表明,以中国式护士排班问题为例,对比IP＋VNS（variable neighborhood search）和hybrid EA等四类主流算法,IP＋EA混合算法能求得更高质量的解。因此,在此类NP难问题的求解上,IP＋EA混合算法比其他四类算法具有更明显的优势和效果。

英文摘要：

NRP is a NP-hard optimization problem with multiple constraints. Many algorithms are difficult to make a balance between computational time and solution quality to solve NRP problems. For this problem, this paper proposed a hybrid algorithm framework of integer programming and evolutionary optimization to solve NRP problems following two steps. First, it used the integer programming to solve a brief NRP to produce high-quality initial solutions. Second, it optimized the initial solutions by evolutionary algorithm in advance to achieve an improvement. The experimental results of Chinese NRP indicate that the hybrid IP ＋ EA algorithm is able to obtain solutions of higher quality than IP ＋ VNS, hybrid EA and other two popular algorithms. Therefore, on solving this type of NP-hard problem, the hybrid IP ＋ EA algorithm is more efficient than the other four algorithms.