护士排班问题是一类多约束条件下的组合优化的NP难问题,即给定一个护士集合、一个班次集合和一个约束集合,在一个时间周期内,将具有不同技能的护士分配到每天的班次中,同时充分考虑各种约束条件的影响,以期编排出一个科学合理的排班方案。好的排班可以兼顾护士的工作和生活需求,提高护士的工作效率,优化医院的人力资源配置,并且相关算法也可以应用到其他资源调度问题中。排班问题涉及到的约束较多,问题的复杂度较高。当前,大多数医院的护士排班工作都是通过手工完成的,即耗费时间,又不能得到一个高效的排班方案。因此,如何在合理的时间内制定一份科学高效的排班表成为医院急需解决的问题。本文针对这一问题展开研究。近年来,科研人员提出各种各样的求解护士排班问题的算法,现有的自适应邻域搜索(Adaptive Neighborhood Search,ANS)算法是其中一种较好的变邻域搜索算法。针对不同的用例,ANS算法都能够求得最优解或次优解,但它的缺点是,计算时间长。为了克服ANS算法计算时间长的缺点,基于单目标优化模型,本文提出一种并行的自适应邻域搜索(Parallel and Adaptive Neighborhood Search,PANS)算法。本章算法的创新点在于:(1)设计实现一种的新的初始化算法;(2)改进ANS算法的邻域搜索顺序;(3)对ANS算法进行并行化处理。实现结果显示,相比ANS算法,改进后的PANS算法求得的解的平均值更优,并且算法的运行时间更短。已有的求解护士排班问题的算法都是单点启发式算法,即算法在求解过程中始终基于单个解向量进行寻优。该类型算法的缺点是,迭代次数多,求解的时间长。针对这些缺陷,本文提出一种新的两步骤优化(Two Steps Optimization,TSO)算法来求解护士排班问题。在第一步优化过程中,算法采用遗传算法快速收敛,得到一个局部最优解集,在第二步优化过程中,本文设计了一种扰动和修复算法,首先对第一步得到的局部最优解集进行扰动,随后对某些班次重新分配护士,使算法跳出局部最优,得到全局最优解。实验表明,新的两步骤优化算法在牺牲解的部分精度前提下,大大缩短了求解的时间。