基于细菌觅食算法的排班智能优化

张永棠

摘 要：智能排班问题是极为复杂的组合优化问题。它包含了劳动法约束、员工层级、不同层级的工资策略、不同班次的工资策略、资源需求等复杂因素。我们以南昌某医院护士排班智能优化为例，选取了基于细菌觅食优化的算法来为此类问题进行优化求解。为了提高算法的搜索能力，将信息交流机制加入到细菌在趋化过程中的翻转方向选择上，研究了基于四种静态拓扑结构和一种动态拓扑结构的邻域结构下的细菌觅食优化算法。

关键词：智能优化 群体智能 调度 细菌觅食算法

中图分类号：TP18 文献标识码：A 文章编号：1672-3791（2018）01（b）-0031-02

随着人们对于健康保健意识的日益增强，患者及家属对护理服务的需求不断提高。如何有效分配护理资源管理、为病人提供高品质的服务并有效控制预算是当今当前医院护理管理所面临的重大课题。但是在实际中，劳动法规约束、个人能力的差别、应急性、工作时间不稳定等因素导致实现较好的护理管理困难重重。

智能排班问题（Intelligent Rostering Problem，简称IRP）是指在给定的排班时间段内为特定的一组员工安排班次，并使该排班方案满足各种硬性约束条件，同时尽量满足各种软性约束条件，并在此基础上优化相关性能指标。因此，智能排班问题是一个极为复杂的组合优化问题，也是现代人力资源管理亟待解决的一大难题。

1 排班问题

本文研究以南昌某医院的护士排班问题为例。在给定的一个排班周期内对于一定数量的包括不同等级的护士进行排班安排。需要考虑的条件有：满足国家劳动法规定、医院一系列约束条件，满足医院工作需求，护士合理要求。本文研究的护士排班问题主要有以下特点：

（1）护士每天的工作分为三种班次，分别为早班（0点～8点）、白班（8点～16点）、晚班（16点～24点）。

（2）护士工资按照技术资格（初级、中级、高级）分配。其中如果低级护士工资为1，则中级护士工资为1.2，高级护士工资为1.5。

（3）同时由于夜班比较辛苦，因此对于夜班工资具有一定的补偿。如果早班、白班工资为1，则夜班工资为1.5。

除了上述特点，护士排班问题还必须满足一定的约束条件，其中必须满足的硬约束条件为：

HC1：排班周期内，每天每个班次必须安排护士；

HC2：每个护士每天只能上一种类型的班；

HC3：每个护士在相邻2天的班次不能出现连续排班；

HC4：在一个排班周期内，最长工作时间不能超过规定的上限；

HC5：在一个排班周期内，最短工作时间不能少于规定的下限；

HC6：高级护士可以替代中级、低级护士，中级护士可以替代低级护士，反之不行。

尽可能满足的软约束为：

SC1：任何一个班次（早班、白班和夜班）的各级护士数不低于实际需求量。

2 基于细菌觅食优化的算法

细菌觅食优化算法是受大肠杆菌觅食的启发提出来的。它包含趋化行为、游动行为、繁殖行为、死亡-驱散行为四种基本的行为。通过这四种行为，细菌进行位置迭代，寻找到最优的适应度值。

结构重组的细菌觅食优化算法（Structure-redesign-based Bacterial Foraging Optimization，SRBFO）是基于BFO算法的一種改进算法。原始BFO算法中，4个操作算子组成了三层嵌套循环结构，每一次计算都需要遍历三层循环，导致算法计算复杂，收敛速度缓慢，计算耗时长。因此，Niu等人针对这一缺点，从GA、PSO以及其他智能算法中获取灵感，将单循环结构引入到原始BFO算法中，代替原来的三层嵌套循环结构，提出了SRBFO算法。在SRBFO算法中，复制操作、死亡-驱散操作均与趋化操作并行进行，从根本上简化了算法的计算复杂性。目前已有相关的研究成果已经证明的该算法在函数优化和现实问题优化求解上的有效性，详细情况见文献。

细菌信息交流机制最重要的就是细菌与其他细菌之间的相连，从而实现信息的传达。不同邻域结构的SRBFO算法的效果会有很大的差别。因此，借鉴Kennedy等在文献中首次提到的粒子群算法中的拓扑结构，本文拟将选取5种拓扑结构加入到SRBFO算法中，其中4种分别为：环型（SRBFO-R）、星型（SRBFO-ST）、全连接型（SRBFO-FC）、von Neumann（SRBFO-VN）型；另外一种为动态拓扑结构（SRBFO-DN），其拓扑结构是通过一定的概率条件在星型和环型之间转化。这五种拓扑结构主要加入在趋化过程中细菌在翻转时的方向选择上，通过与邻域的细菌进行交流学习来选择自身的翻转方向。

3 优化求解

为了求解本文所研究的护士排班调度问题，采用考虑了不同信息交流机制的结构重组的细菌觅食优化的算法对此进行求解，主要包括三大步骤：粒子编码、方案可行化、目标函数构建等。

3.1 粒子编码

对于算法而言，每一个粒子应该是一个潜在的可行解，即每个粒子所携带的信息必须包括所有待调度的护士的排班安排，因此在Matlab中编码时，将每个粒子设为一个元胞，即每个粒子是1*nn（nn为总护士数）的矩阵，在该矩阵中的每个元素为ss*sd矩阵（ss为班次数，一般加上休班，ss=4；sd为调度周期），如下所示：

该编码所代表的信息为：

3.2 方案可行化

细菌觅食优化算法是求解连续的优化问题，对于排班调度这种离散问题，必须通过一定的机制将迭代后的位置值转化为离散的，才可以成功应用于求解护士排班问题。因此在粒子编码时，每个粒子的编码是ss*sd的矩阵，通过最小位置值的解码方式，将矩阵中的每一列的元素都转换为0-1，同时满足每一列中有一个1、3个0（此转换后的方案直接满足约束条件HC1、HC2），该元素1所在的行则代表该护士在调度周期的某一天的班次，如果为第1行，则表示该天的班次为早班，如此类推。

3.3 目标函数构建

护士排班调度问题的原始目标函数为使得总护士工资成本最小，同时为了尽可能满足软约束SC1，通过罚函数的方法将未满足的需求加权到目标函数中，本文中惩罚系数设为1000。但是HC6规定高级护士可以替代中级、低级护士，中级护士可以替代低级护士，反之不行。因此在计算未满足的需求成本时，必须分层计算，从低级护士开始计算，如果低级护士排班方案中的某个班次数量低于需求，则计算中级护士，如果中级护士在该班次的排班数量大于需求，则剩下的班次可以用来填补低级护士排班方案中所未满足的需求，如此类推，最后计算总的未满足的需求，并计算总的未满足的需求成本。

4 结语

本文针对我国目前的情况，考虑了劳动法约束、护士层级、不同层级的工资策略、不同班次的工资策略等因素，对护士排班问题进行了研究。为了优化求解这类NP-Hard问题，本文提出了基于交流机制的结构重组的细菌觅食优化算法来对这一问题进行优化求解。将四种静态拓扑结构：环型、星型、全连接型、von Neumann型以及一种动态拓扑结构分别加入到细菌在趋化过程中的翻转方向选择上，以提高算法的搜索能力。从整体上来看，本文不仅扩展了细菌觅食优化算法的应用范围，同时为护士排班这类NP-Hard问题的优化求解提供了更多借鉴。

参考文献

[1] 童向红，徐兰玲，张娃莲.内科护士排班模式改进与效果分析[J].浙江医学教育，2008（4）：24-25.

[2] 范淑玉，杨向红.我国护士排班状况研究进展[J].护理管理杂志，2008，8（12）：27-29.

[3] 刘梅，廖少玲，文若兰.护士排班的研究现状[J].广东医学院学报，2011，29（2）：210-211.