摘要：护士排班问题是一类多约束多陷阱问题，传统的计算方法和启发式算法往往很难找到其最优解。采用基于遗传算法GA和可变邻域搜索算法VNs的混合策略对护士排班问题进行了求解。其中，GA算法通过添加判断准则和控制策略来有效生成新的护士排班表，而VNs策略则实现初始化、约束条件下的杂交变异和解空间的分离等运算。最后，对20组基准护士排班问题进行了求解，并将求解结果与国际上近年提出的IP＋VNS方法进行了比较，实验表明，在相同的计算时间内，GA＋VNS算法的求解效果明显更优。

关键词：护士排班问题 遗传算法 可变邻域搜索算法 

单位：乐山师范学院物理与电子工程学院 四川乐山614000 华南理工大学计算机科学与工程学院 广东广州510006 华南理工大学软件学院 广东广州510006