基于整数规划与演化优化混合的护士排班问题求解算法

• 作者: 卓晓燕 林伟佳 欧阳骥 秦勇 黄翰
• 来源期刊: 计算机应用研究
• 关键词: 护士排班问题 混合算法 整数规划 演化算法
• 年，卷（期）: 2015,（12）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3660-3664
• 页数: 5页
• 分类号: TP181
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2015.12.031

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄翰	华南理工大学软件学院	50	526	11.0	21.0
2	欧阳骥	东莞理工学院计算机学院	12	31	3.0	5.0
3	林伟佳	华南理工大学软件学院	3	12	1.0	3.0
4	秦勇	东莞理工学院计算机学院	25	98	6.0	8.0
5	卓晓燕	华南理工大学软件学院	2	11	1.0	2.0