一种智能高效的并行护士排班算法

王 陟，李雁妮

(西安电子科技大学 计算机科学与技术学院，陕西 西安 710071)

护士排班问题(Nurse Rostering Problem, NRP)是一类多约束条件下的组合优化NP难问题[1]，即给定一个护士集合、一个班次集合和一个约束集合，在一个时间周期内尽可能地满足各种约束条件，将具有不同技能的护士科学合理地排班到该时间周期内的每天的班次中。好的排班不仅可提高护士的工作效率，优化医院的人力资源配置，并且其算法也可以应用到其他资源调度问题中[2-3]。针对护士排班这一NP难问题，国内外众多学者展开研究，相关国际化组织也分别于2010年及2014年成功举办了两届世界护士排班大赛[3-4]。护士排班及其他组合优化问题多采用智能优化算法进行求解，这些算法主要分为两类：精确算法[5-6]和启发式算法[7-16]。精确算法可找到全局最优解，但计算时间复杂度高，且不适合求解大规模的护士排班问题。因此，目前较为流行的护士排班算法大多采用启发式优化方法，以期在一个合理可行的时间内找到问题的最优解或次优解。Awadallah等[8]基于和声搜索与爬山法相结合等优化策略，分别提出了一种较好的护士排班算法，但其算法解的质量及时间性能还有待于提高。为了广泛搜索并加快问题寻优，Lü和Zheng等[9-10]采用自适应/随机变邻域搜索策略，分别提出了两种高效的护士排班算法ANS[9]和RVNS[10]。为了有效地应对护士排班这一NP难问题，并进一步提高护士排班问题算法的性能，文献[11-14]采用不同的优化策略进行了积极大胆的尝试与探索。近年来，开始出现将精确算法和启发式算法相结合的较好的护士排班算法[15]。但现有算法主要存在以下缺陷：①采用随机策略生成的算法初始解质量不稳定；②算法搜索方法单一或者搜索策略不尽合理，导致算法易陷入局部最优，全局寻优能力较差；③除RVNS算法外，现有的算法均不适合大规模的护士排班问题，且所有算法均为串行算法，解的质量和时间性能都有待于进一步提高。

针对护士排班这一NP难问题并为了有效克服已有算法的缺陷，笔者提出了一种新的高效并行护士排班算法(Intelligent and Efficient Parallel Nurse Rostering algorithm, IEPNR)。IEPNR首先采用启发式排序随机生成问题的初始解，以获得高质量的算法初始解；然后，采用并行自适应多样化变邻域搜索和增量式计算来快速寻优。同时，采用随机扰动与禁忌列表以使算法有效逃离局部最优并避免冗余计算。大量的标准测试数据集上的仿真实验结果表明：IEPNR算法在平均解质量和运行时间上均远优于现有最好的护士排班算法——ANS和RVNS，且更适合于大规模护士排班问题。

1 护士排水问题的形式化描述及问题优化模型

给定护士集合S={s1,s2,…,sn}，日期集合D={d1,d2,…,dm}，班次类型集合H={早班，中班，晚班}，护士排班问题可形式化地描述为：在给定必须满足的若干硬约束(Hard Constraint, HC)和最大化地满足若干软约束(Short Constraint, SC)的前提下，给出一个护士排班问题的可行解，即护士排班表X|S|×|D|={xi,j|xi,j∈H,1≤i≤|S|,1≤j≤|D|}。

根据第一届护士排班大赛中的规定，在护士排班问题中，必须满足的硬约束共有两个，分别记为HC1和HC2。其中，HC1：在一个时间周期内的每一天，必须满足所有班次所要求的护士类别(护士长、高级护士、普通护士)及相应人数；HC2：一个护士每天最多只能安排班次类型集合H中的一种。应最大化地满足的软约束共计18个，分别记为SC={sc1,sc2,…,sc18}。如sc1/sc2，在一个排班周期内一名护士的最大/小工作天数约束；sc3/sc4，在一个排班周期内一名护士的最大/小连续工作天数约束，等等。具体的sc1～sc18的定义及形式化描述请参见文献[3]。

(1)

2 一种智能高效的并行护士排班算法

为了清楚地论述IEPNP算法的思想，首先给出算法的框架，之后详细论述所采取的主要智能优化与加速计算策略。

2.1 IEPNR算法框架

基于式(1)所构建的护士排班问题模型，提出了一种新型智能高效的两步并行护士排班算法——IEPNR。算法框架如下：第1步，将随机生成的满足硬约束的可行初始解中的每个排班护士的违约度值按降序进行排序，采用启发式方法调整/替换高违约度的护士排班项，从而获得一个较高质量的算法初始解(由算法的Optimal_Initial()函数实现)；第2步，采用并行智能多样化变邻域搜索和增量式计算在搜索范围内快速找到最优解。同时，采用随机扰动与禁忌列表以使算法有效逃离局部最优和避免冗余计算。最终，在可行的时间内，找到问题的最优解或次优解(由算法的Intelligent_Search()函数实现)。

算法1一种智能高效的并行护士排班算法。

输入: Problem instance;

输出: The best solutionX*;

① ReadS,D,H,HC1,HC2,andSC;

②X0←Optimal_Initial(S,D,H,HC1,HC2,SC);

③X*←Intelligent_Search(X0,S,D,H,HC1,HC2,SC);

④ returnX*。

算法2Optimal_Initial(S,D,H,HC1,HC2,SC)。

① Randomly select halfD1ofD, and randomly initial the shifts of the solutionX0onD1subjecting toHC1andHC2;

②D2←D-D1;

③ Sort the shifts of a random date d ofD2in descending order by the number of nurse required;

④ Assign shift of d to the nurse n of the unassigned nurse set in ascending order byfn(X0);

⑤ Adjust shifts onD1according to Line 3-4;

⑥ returnX0。

算法3Intelligent_Search(X0,S,D,H,HC1,HC2,SC)。

①Lt←Ø;dl←0;i←0;

② repeat

③Xi+1←Xi;

④ Select moves to optimizeXi+1by using search strategies withdlandLt;

⑤ UpdatedlandLt;

⑥ Calculatef(Xi+1)in parallel;

⑦ iff(Xi+1)can not be improved then

⑧ Randomly perturbXi+1;

⑨ else iff(Xi+1)reaches the improvement cutoff then

⑩ break;

下面将对所提出的IEPNR算法中的主要优化和加速计算策略进行论述。

2.2 基于启发排序的高质量初始解

目前大多数护士排班算法都采用满足硬约束的条件所随机生成的可行解作为算法的初始解。该方法的优点是实现简单，但其初始解的质量无法保证。笔者的理论分析和大量实验结果表明：一个较高质量的初始解能够缩短算法的优化时间。因此，IEPNR采用启发排序方法来获得一个较高质量的初始解，实现过程Optimal_Initial()的具体步骤如下：

第1步 随机选择排班日期集合D的一半D1，在满足硬约束的条件下随机生成在D1时间期内的护士排班表X0。

第2步 在X0剩余排班日期集合D2=D-D1中随机选取某一天，将该天班次按所需人数进行降序排序，然后依此顺序将未分配排班护士且违约度升序的顺序安排进该天的各班次中。

第3步 对X0中D1时间段内的每天已随机生成的可行排班，按照第2步的方法进行优化排班调整，直至D1中的每天排班都调整完毕为止。输出较高质量的可行初始解X0。

2.3 智能的多样化变邻域搜索策略

IEPNR主要通过智能多样化变邻域搜索策略以及增量和并行计算方法来加速算法的性能。下面先给出相关的基本概念，之后再进行详细论述。

定义1位移。对于一个护士排班问题的可行解X，将其中某天d(d∈D)已排班的两个护士i和j的班次互换，或将有班次的护士i的班次安排给还未排班的护士j称作一个位移，记为m(d,i,j)(简记为m)。X上可执行位移的集合记为M(X)。若两个位移m1和m2(m1,m2∈M(X))，其各自对应的日期及排班护士互不相同，则称m1和m2互不相关；否则，称其相关。

定义2邻域。给定护士排班问题的一个可行解X，在X上的一次m运算记为X⊕m，则X的邻域为

N(X)={X⊕m|m∈M(X)} 。

(2)

定义3违约度增量。对于一个可行的X，执行一次或若干次位移m(m∈M(X))后,某护士的违约度fn(X)或X总的违约度f(X)的改变量称为违约度增量，分别记为Δfn(m)和Δf(m)。

定义43种变邻域搜索。在X上可执行位移操作集M(X)中的任一元素m(d,i,j)。当满足d∈D，护士i∈S,j∈S时，由于m可在整个D和S中进行搜索，故在此大邻域的搜索称为密集搜索；当i∈S*,j∈S*时，S*⊆S，由于m只能在S中的子集S*进行操作，故该搜索称为过渡搜索；当i∈S*,j∈S*时，S*⊆S，对于随机选择的护士i和j所进行的一个位移操作m，不要求其Δf(m)有所下降，但其m会使护士i和/或j的某个/些对软约束的违约值下降，则该搜索被称为多样化搜索。

IEPNR算法通过对以往搜索计算结果的学习，智能地在定义4中的3种不同的变邻域搜索策略中进行切换，主要通过其创建的禁忌列表Lt和多样化水平参数dl(dl∈[0,1])来达到智能搜索与切换，同时避免其中的冗余计算，最终达到广泛搜索并快速寻优的目的。

多样化参数dl用于算法IEPNR，能以定义4中的3种不同变邻域搜索寻优并进行智能切换。IEPNR运行过程中：

(1)dl赋初值为0，以密集搜索方式迅速优化初始解X0。当算法的密集搜索已无法使当前解的违约度再降低时，则d1值以步长λ·(1-dl)进行递增。当dl∈[0，α](α=0.30)时，执行密集搜索。

(2)当dl∈(α,β](β=0.65)时，算法执行过渡搜索。当算法的过渡搜索已无法使当前解的违约度再降低时，dl以步长λ·(1-dl)进行递增。

(3)当dl∈(β,1]时，算法执行多样化搜索。当算法的多样化搜索已无法使当前解的违约度再降低时，dl值以步长λ·dl进行递减，直至算法切换至密集搜索。

(4)同时，算法规定，在一定迭代次数内无法使当前解的违约度降低或搜索策略切换较为频繁时，算法将强行设置dl值为1，算法结束本轮迭代搜索，为跳出局部最优解进行随机扰动。

在IEPNR算法中，当λ取值较大时，搜索策略切换频繁，导致解的质量不稳定；当λ取值较小时，搜索策略无法有效地进行切换，算法效率较低。通常，经验性地设定λ=0.1。

IEPNR算法中智能化的多样化变邻域搜索过程Intelligent_Search()主要实现步骤如下：

第1步 创建禁忌列表Lt=Ø，置参数dl=0，算法迭代初值i=0。

第2步Xi+1←Xi，基于Lt和dl，并采用上述智能的多样化变邻域搜索策略进行循环迭代对Xi+1进行优化。陷入局部最优了吗？是，转第3步；否则，Xi+1达到期望值吗？是，转第4步；否则，i←i+1,继续循环迭代寻优。

第3步 对Xi+1进行随机扰动，i←i+1,转第2步。

第4步X*←Xi+1，输出最优解X*。

2.4 增量并行的高效计算

通过前面的论述已知，护士排班问题是一个组合优化的NP难问题。特别是当问题规模增大时，例如，护士集合S，或者排班日期集合D,或者软约束集合SC的规模增大，或者它们组合增大时，问题的搜索空间将极其巨大，导致问题无法在可行时间内进行求解。为了应对大规模的护士排班问题，笔者提出了以下高效的计算方法。

2.4.1 并行计算多个位移违约度

通过定义1，并经分析和证明，得到了引理1。

引理1位移可加性。对于某个可行解X，X上的k(2≤k≤|S|/2)个互不相关的位移操作m1,m2,...,mk同时执行时，其违约度增量Δf(m1,m2,...,mk)等于其违约度的增量之和：

(3)

基于上述引理，提出了在一次迭代寻优过程中，可将k个m改为一次搜索选取k个互不相关的m，然后同时在排班表中对它们进行高效操作的方法。该方法不仅可以k倍提高搜索计算效率，而且大量的实验结果也表明：单次选取多个位移操作不仅使得算法优化收敛更快，并且可以增加跳出局部最优解的概率。

2.4.2 增量计算

在算法优化迭代计算时，在某次迭代的一个候选可行解Xi执行一个位移操作m后，则得到的Xi′的违约度为

f(Xi′)=f(Xi)+Δf(m) 。

(4)

不同于现有的护士排班问题算法大多采用每执行一个位移操作m，均需从零开始计算其总违约度值的方式，IEPNR的增量计算彻底消除了冗余计算，大大地提升了算法的时间效率。

2.4.3 并行计算

通过理论分析与实验结果表明：算法中最耗时间的计算是排班表中其表项违约度的计算。幸运的是，各项软约束的计算彼此之间互不干扰。因此，为了进一步提高算法计算的效率，采用MapReduce并行编程思想。首先将每个护士的排班表和软约束违约度计算任务进行切分，分配给一个空闲线程，然后将每个线程的计算结果再归约求和，得到最终的排班表的总违约度值。

3 实验结果及分析

3.1 实验软硬件平台及测试数据集

实验的硬件平台为Intel Core i7-7700 4核8线程CPU 3.6GHz，RAM 16GB，Win10(64位)，软件平台为jre-8u144。为了具有比较的公平性，IEPAN算法及所比较的ANS和RVNS算法采用同样的软硬件平台进行实现和测试。实验数据集选取INRC-2010竞赛测试集[10]中最具有代表性的9个案例。其中有sprint、medium和long这3种类别，护士规模为10，30，50，依次增大。上述类型又由early、late和hidden这3种不同的软约束集合从简到难构成。

3.2 实验结果及分析

表1展示了ANS、RVNS和IEPNR算法在9种不同的标准测试集运行10次的平均违约度值favg、平均迭代次数iavg和平均运行时间tavg。

表1 ANS、RVNS与IEPNR算法性能对比实验结果

注：“-”表示算法平均运行时间远大于24h，无法给出运行结果。

图1 IEPNR算法与RVNS算法计算性能对比示意图

从表1和图1中可以看出，IEPNR算法在平均解质量上均远优于现有最好的护士排班算法ANS和RVNS。与ANS算法已求解出的7个案例相比，IEPNR算法的平均违约度最大降低了139.7，平均降低了34.4；与RVNS算法的平均违约度相比，IEPNR算法的平均违约度最大降低了36.4，平均降低了17.8。实验结果表明，IEPNR算法中智能化的多样化变邻域搜索策略是合理有效的。

在运行时间方面，IEPNR算法的运行时间随着测试案例规模扩大而增长较缓，RVNS算法的运行时间增长较快，而ANS的运行时间呈指数级增长。对于long类型的大规模案例，ANS算法已无法有效求出可行解。从图1(c)中可以看出，与RVNS算法相比，其单线程的运行时间比之要少；IEPNR算法在8线程时其算法平均运行速度要比RVNS快3.8倍。实验结果充分证明了IEPNR所采用的并行增量式计算策略是高效可行的。

为了进一步对比3种算法的单次迭代计算性能，选择平均违约度值较为接近的案例medium_early进行多次试验。从表1的实验结果可算出，ANS算法单次迭代所需平均时间为87.13 ms，RVNS算法单次迭代所需平均时间为1.70 ms，IEPNR算法1线程单次迭代所需平均时间为1.69 ms。与ANS算法相比，缩短到1/50的时间。说明IEPNR算法在单次迭代中的计算量要远远少于ANS算法，并且证明了IEPNR所采用的增量式计算方法可有效减少单次迭代的计算量。

4 总 结

针对护士排班这一NP难问题，并为了克服已有算法的缺陷，首先将问题建模抽象为一个单目标优化问题，之后基于所提出的一系列优化策略，如启发式排序、禁忌与智能多样化搜索、增量与并行计算等，创新性地提出了一种智能高效的两步并行护士排班算法——IEPNR。在标准测试数据集上的测试结果表明：IEPNR算法不仅大大优于目前已有最好的护士排班算法，而且更适合于大规模护士排班问题的求解。从现有公开文献来看，这是第一个并行高效的护士排班算法。下一步的努力方向是，将IEPNR优化改造为一分布式并行算法，以进一步提高算法的时间性能；另外，进一步精化与抽象问题模型与问题求解算法，以使算法适用于一般大规模的资源调度问题的求解。