护士排班问题

1、管理系统建模与优化期末作业护士排班问题专业：管理科学与工程时间： 2015 年 1 月目录1案例背景 32研究现状 33案例模型 43.1护士排班问题 .43.2护士排班模型 .44护士排班算法 74.1整数规划 .74.2模拟退火算法 .74.3整数规划与模拟退火混合算法 .85案例计算与分析 105.1案例数据 .105.2分支界定法计算结果 .135.3模拟退火算法仿真结果 .135.4分支界定与模拟退火算法混合仿真结果 .146结论 15参考文献 16护士排班问题1 案例背景护理工作是整个医疗卫生工作的重要组成部分， 在医疗实践中担负着特殊的工作和任务，是整个医院开展医疗服务的运营基础

2、。目前各国护士短缺严重，已引起了国外护理管理的高度重视 1 。我国护士长期处于特殊的环境氛围和接待各种病情的患者， 并承受超负荷的工作和长期紧张脑力劳动、不规则的排班等护理状况，它将直接影响护士的身心健康，影响工作质量，造成护患关系的紧张 2 。科学管理护理资源，有效控制医院护理成本预算和提升患者满意度是目前研究的热点课题 3 。在目前护理工作量大、 应急性险强、不规则轮班，传统的单一的简单排班模式的情况下，由于医院存在控制成本的压力，造成了医院和护士的利益冲突和目标差异，为更好的调高护理质量、降低医院护理成本，需要建立一个完整的带有劳动法规约束和满足护士自身需求的护士排班模型以及护士排班算法

3、。护士排班问题主要是指在现有医疗资源的约束条件下，从医院的护理成本、护士的满意度、班次的偏好、降低护士工作压力和改善护士身心健康等方面，编制出科学的排班表，从而有效改善排班表的质量和提升护理工作的满意度和社会形象42 研究现状国外对护士排班问题的研究起步较早，护士排班问题已经被临床研究机构和计算机方面研究多达 40 余年了，护士排班问题是建立在一系列的劳动法规和班次需求约束下的复杂组合优化问题，属于 NP 问题 5,6,7 ，目前可行的主要技术是数学规划8,9,10,11,12和启发式算法 13,14,15以及传统数学规划和启发式算法的融合技术， 但是国外的劳动法规与护士工作状况与国内完全不同

4、，模型和约束条件与国内存在明显的差异。而国内护士排班问题研究起步较晚， 主要是按功能模式和整体护理模式排班， 按固定、弹性、“三班制”、 APN ”排班，护士自我排班等简单手工排班模式 16 ，而定量排班的 ILP 模型的约束条件并未考虑“ APN ”等机制和排班公平性等，难以综合考虑以病人的需要为中心、互补增值、均衡平等、稳定机制、人性化原则，故缺乏一套有效的模型优化机制。由于一系列约束条件和护士的偏好,整个护士排班模型是复杂的组合优化问题,比 TSP 问题更难的 NP 问题 ,解决此问题能有效推动调度算法的改进。 随着现代医院的发展 ,医院资源的资源紧缺和护士短缺以及护士自身的潜在需求 ,

5、迫切需要实现信息化的护士排班系统 ,从而有效的改善护士的管理和工作状况 ,整合医院的资源优势 ,更好的为患者服务 ,有效改善医患关系 ,促进社会的和谐发展。3 案例模型3.1 护士排班问题护士排班问题是一种满足系列劳动法规和班次约束的护理资源最优分配问题。在实际的护士排班中，约束条件主要包括工作强度要求、夜班班次要求、护士对工作环境的满意度、工作时段的偏好和排班公平性等。护士排班问题的目标就是在一个排班周期内(一周或一月 )，满足一系列劳动约束和医院资源需求的约束，使得整个医院的护理成本最小化和护士工作的满意度最高。护士排班问题要服从以下的三个关键假设:（ 1）护士排班模型的约束条件必须符合我

6、国现行的劳动法规和大型医院护理工作实际状况。（ 2）护士的自身的要求要尽量去满足，这对于护士排班问题的研究是很重要的。（ 3）没有必要把在岗的所有护士都考虑在护士排班模型之中。 那些实习和兼职的护士可以实行排班后，根据实际情况动态调整到护士排班表中。自从 2008 年 5 月 12 日新护士条例颁布实施后，我国大部分医院实行“ APN” 时间排班制。 APN ”时间制，即每天平均分为 3 个班次 :其中 A 班(8:00-16:00),P 班（ 16:00-0:00),N 班 (0:00-8:00 ，若将“休班”定义为 R(rest)班，那么护士的排班主要指A 班、 P 班、 N 班和 R 班

7、。其中“ APN”充分保证了高峰时段的护理安全。强约束条件 (Hard Constraint,HC)是在我国任何医院的护士排班环境中都必须满足的约束条件，否则整个排班表就不可行。强约束条件主要考虑劳动法规、医院的护理资源和班次约束等 :HC1: A 班和 P 班均有 1-2 名中级资质以上的护士 ;HC2: 任何一个班次 (A 班、 P 班和 N 班 )的护士数不低于实际需求量 ;HC3: 每位护士一天最多只能进行一个班次的工作;HC4: 任何护士在相邻 2 天的班次不能连续 (若第 1 天排 N 班，则第 2 天不能排 A 班);HCS: 在一个排班周期内，每位护士的最长工作班次不能超过规定

8、的上限;HC6: 在一个排班周期内，每位护士的最短工作班次不能少于规定的下限;HC7: 在一个排班周期内，每位护士的最长连续N 班不能超过规定的上限 ;HC8: 在一个排班周期内，每位护士的最长连续班次不能超过规定的上限;弱约束条件 (Soft Constraint, SC)是指在医院实际护士排班中尽可能多的去满足的条件，各所医院在实际排班巾将弱约束条件进行调整和增加，本文中主要考虑护士的周末休息和排班的公平性 :SC1:尽可能多的护士在周末至少休息一天;SC2:不对某个护士特殊照顾A 班;如果护士的排班表满足了所有的强、 弱约束条件， 则为可行的护士排班表， 如表 3-1 所示 :3-11A

9、APRNNR2RANNRPNNPNNRAAR3.2 护士排班模型护士排班模型的目标就是在一个排班周期内(一周或一月 )，满足一系列劳动法规、医院护理资源需求和班次约束条件下， 使得整个医院的护理成本最小化和护士工作的满意度最高。旨在降低医院的护理运营成本，同时有效降低护士工作压力，让护士更好的处理好工作、生活和家庭的关系、从而提高医院的护理工作效率。参数假设 :表示 n 名护士集合 ;表示一个排班周期内的天数集合 ;表示每天班次的类型 (A,P,N,R);m 表示在一个排班周期内，每位护士的最长工作时间;w 表示在一个排班周期内，每位护士的最短工作时间;1 表示在一个排班周期内，每位护士连续夜

10、班的最长时间;n;2 表示在一个排班周期内，每位护士连续班次的最长时间ncijk 表示第 i 位护士在第 j 天选择第 k 个班次工作的工资等级，记为 cijk =1,2,3,4,5; djk 表示在第 j 天第 k 班次对护士的需求量 ;pik 表示第 i 位护士对第 k 个班次的工作满意度， 记为 pik=1( 非常不满意 ),2(不满意 )， 3(一般 ),4(满意 )， 5(非常满意 );xijk =1 表示第 i 位护士在第 J 天安排第 k 个班次，反之 xijk =0;中级及以上职称，其他 1 表示工资成本权重系数，其中凡 1 0,1; 2 表示班次满意度权重系数，其中 2 0,

11、1;基于上述定义的参数，我们建立如下护士排班模型:其中s.t.HC1:HC2:HC3:HC4:HC5:HC6:HC7:HC8:SC1:SC2:护士排班模型要求在任何排班中强约束条件都必须满足，并尽可能多的满足弱约束条件。可根据实际环境中的重要性程度将弱约束做出如下的顺序 :SC1 SC2，其中“ ” 表示优先级，优先级的顺序由医院决定。由此可将目标函数 (3-1)化为 :其中s.t.HC1:HC8， SC1，SC2模型 (3-14)是一个典型的0-1整数规划模型，包含4*n*J个0-1决策变量，以及(17+2n)J+(2+n1+n2)n 个约束方程。由于是在固定周期 T 内进行 n 位护士排班

12、，并假设每日分 4 个班次，故模型的求解难度与护士数量呈线性关系。4护士排班算法4.1整数规划整数线性规划 (IntegerLinear Programming, ILP) 是最优化理论中比较重要的体系，在工业和工程设计和科学研究方面、计算机设计、系统可靠性、编码和经济分析等诸多领域有广泛应用。但是整数线性规划问题属于 NP 难问题，一般不存在多项式算法，目前求解 ILP 的方法主要有分支定界法、割平面法、多面体法、列生成法、禁忌搜索和遗传算法等 53,54,55 。在求解整数线性规划问题中， 分支定界算法是一种最常用的方法，分支定界 (branch and bound) 算法在问题的解空间上

13、采取树形搜索整数规划问题的方法。分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同， 分支定界算法采用广度优先或最小耗费优先的方法在解空间搜索树，并且在分支定界算法中，每一个活结点只有一次机会成为扩展结点。对于大规模整数规划问题 (IP ，直接采取举例法相当的困难，采用“分而治之” （ divide and conquer ）的策略，先将可行解区域划分为一些小的解集合，然后在较小的解集合上求解相应目标函数的最优值，并将所求结果集成在一起生成原问题的最优解。在求解较小的解集合对应的子问题时，既可以采用分而治之的策略进行分析，也可以采取

14、其方法对子问题进行求解。分支定界算法的基本思想是从原问题 (IP) 的线性规划松弛解 X 出发，若最优解不符合原问题的整数条件，那么该解 X 必是原问题的上界 ，而原问题的任何可行解都看作是目标解的一个下界 。它将可行解区域划分为若干子区域，并逐步缩小上界 和增大下 *对于 0-1 整数规划问题的分支定界算法步骤如下所示:0-I整数规划问题分支界定算法流程58步骤 1( 初始 ): 求解原问题 (IP) 的线性规划松弛解，若得到整数解，则视为原问题的最优解，否则得到原问题的一个上界;步骤 2( 分支 ): 选择适当的变量 xi ，分别固定 xi =0 和 xi =1 得到 2 个子问题 ;步骤

15、 3( 定界 ): 选择一个子问题，求解该子问题的线性规划松弛解;步骤 4( 剪枝 ): 若发生下列情况之一，则停止对该问题进行分支( 剪枝 ):（1）子问题的线性规划松弛解的最优解是整数;（2）子问题不可行 ;（3）子问题的上界等于或小于已知的可行解的目标函数值。步骤 5( 最优性 ): 重复上述过程，直到分支定界树中没有需要考虑的节点( 子问题 ) ，则当前最好的可行解就是原问题(IP) 的最优解 .4.2 模拟退火算法组合优化 (Combinatorial Optimization)问题的目标就是从组合问题的可行解空间求出最优解，一般包含变量、约束和目标函数这三个基本要素。在求解过程中选

16、定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。求解组合优化问题就是在目的函数的解集合里找到最适合的解，这必然要求运用一定的算法去降低求解过程的时间复杂性和空间复杂性。 Kirkpatrick 等在 1982 年结合固体退火过程状态变化的思想， 提出一种类似固体退温过程的有效近似算法一模拟退火算法 (Simulate Anneal ，简称 SA)，以解决大规模组合优化问题遇到的瓶颈。模拟退火算法 58, 59, 60 是解决组合优化问题的算法，它采用 Metropolis 接受准则使算法跳离局部“最优”的陷阱，并使用“冷却进度表”来控制整个算法实施过

17、程，最终使算法能够在多项式时间内得出一个近似最优解。一个优化问题可以描述为 : 其中 S是一个离散有限状态空间， i 代表状态。针对这样一个优化问题， SA算法的计算步骤能够描述如下 :第 1 步 : 初始化，任选初始解，给定初始温度T0 和终止温度Tf ，令迭代指标k=0，Tk=T0。第2步:随机产生一个领域解，（表示的领域），计算目标值增量。第3步:若，令 i=j转第4 步；否则产生随机量 =U(0,1)，若，则令i=j。第 4 步: 若达到热平衡 ( 内循环次数大于n（Tk) 转第 5 步；否则转第 2 步。第 5 步: 降低 Tk，k=k+1，若 Tk T f ，则算法停止，否则转第2

18、 步。上述模拟退火算法流程如图4.1 所示。图 4.1 SA 算法流程图4.3 整数规划与模拟退火混合算法在护士排班领域研究中，一些算法的混合优化技术已经存在很多年了。国外将整数规划和领域搜索算法的混合优化策略应用于护士排班领域，有效的改善了解的质量和算法的效率。基于上述的研究，本文提出整数规划和模拟退火算法混合优化策略处理护士排班问题的约束条件和护士的潜在要求，从算法的优化机制融合、算法结构互补、优化操作的结合、优化行为的互补和削弱参数的苛刻条件等方面61 阐述了混合优化机制的优越性，其中整数规划的分支定界算法保证了解的可行解，而模拟退火算法以一定的概率接受劣解，从而有效扩大可行解区域，能高

19、效求解组合优化问题。分支定界算法 (BBA) 与模拟退火算法 (SA) 的混合策略，以下简称 BBASA, BBASA 算法其算法流程如下 :步骤 1:状态初始化，确定初温;步骤 2:确定最大点，次大点，最小点;步骤 3:算法收敛准则是否满足，满足就输出结果;否则转到步骤4;步骤 4:使用分支定界算法求出局部极小点:步骤 5:由 SA 利用“护士互换规则”和“班次调整规则”规则产生函数产生新个体;步骤 6:以一定概率接受新个体;步骤 7: SA 抽样稳定，则进行退温操作，跳到步骤步骤 8:退出上述模拟退火算法流程如图4.2 所示。3;否则返回步骤5;图 4.2BBASA 算法流程图5 案例计算

20、与分析5.1 案例数据本文的护士数据来源于 XX 医院护士工作状况调研问卷的调研结果。目前某三甲医院重症科室共有 30 名护士，其中高、中、初级护士分别 3, 5 和 22 位。假设排班周期为一周 (J=7)，并将每天的工作时间平均分为a 班(8:00-16:00, p 班（6:00-0:00）和 N 班(0:00-8:00)三种班次。影响排班质量的主要因素如表5-1 所示。表 5-1排班质量影响因素表序号排班影响因素参考建议1连续上班天数3-4天2连续工作时长3-10小时3连续晚班时长1-2天4排班周期内的总班次4-6天5排班周期内的总工时周工时在 40 小时左右6连续休息天数1-2天7换班

21、的合理性如护士上了晚班之后应该安排休息，不能又安排护士继续去上早班8排班周期内上班工时的平衡要保证在排班周期内每个护士的工时相等9排班周期内上晚班的平衡要保证在排班周期内每个护士上晚班的次数相对公平10排班周期内休息时间的平衡要保证在排班周期内每个护士休息的时间相对公平11要保证在排班周期内每个护士上的各种班次的次数相对公排班周期内班次的平衡平12排班的高规律性护士上班的时间变化相对稳定，不要每天的变动都很大，提供一种人性化的排班由上述排班质量影响因素统计表可知， 每位护士可连续工作的最长时间是 4 个班次，可连续夜班的最长时间是 2 个班次。在一个排班周期内内每位护士最长工作班次至多为6 个

22、班次，最短工作班次至少为4 个班次，在排班周期内的总工时大概在40 小时左右，而每天“ APN ”各班次的实际需求护士数目由科室护士长给定，如表5-2 所示 :周一周二表5-2各班次护士需求人数周三 周四(A/P/N)周五周六周日需求9/6/48/5/39/6/38/5/39/7/410/7/710/7/7XX 医院重症科室采取的是“弹性排班”制，每周的排班表由护士长根据科室的护士需求量和护士的家庭、生活状态等约束手工排班而成，详细的手工排班表如下表5-3所示。表 5-3护士原始排班表序号周一周二周三周四周五周六周日1APRNNAP2APPRAPN3PANRAPA4APNRAAP5PRPRAA

23、P6RRPAPNN7APPRPNN8APPRPAP9PRNNRPA10PRNNRPP11PAARPNR12PAPNPPN13PRAPARN14PRANNRP15NNRAPAP16RNRRPNP17NNRAPAN18NNRPNRA19RPAPRPA20RPAPNRA21RAAPPRP22RAPNRAP23NRPARPA24RPAARNP25RPRPNNN26RNNRRPP27NNRPAPN28RNNRAPP29RAAPRPP30RPPANRA由于每位护士在不同班次内的工资成本是不一样的，定义工资成本为5 个等级， 5代表最高级别的工资， 1代表最低级别的工资， 30位护士的工资级别如下表5-4

24、所示 :表 5-4护士工资表序号职称APNR1中34422初23313中34424初23315初45536中34427初23318初23319初233110初233111初233112初233113初233114初233115初233116中344217初233118初233119初233120初233121初233122初233123中344224初233125高455326高455327中344228初233129中344230初2331每位护士对各个班次的工作满意度是不一样的，定义班次满意度为5 个级别， 1=非常不满意， 2=不满意， 3 二一般， 4=满意， 5=非常满意，为了计算的

25、统一性，将对定义为非常满意，详细的班次满意度表见下表5-5 所示R 班表 5-5护士班次满意度序号APNR1532525325325154251555215625157251585215925151025151152151252151312551425151525151625151725151812551925152025152112552212552352152425152512552612552753252853252925153025155.2 分支界定法计算结果在MATLAB 上用分支界定算法对护士排班模型进行仿真实验，并令1 =0.75，2=0.25，其计算结果如表5-6 所示。表

26、5-6护士排班模型计算结果手工排班表仿真排班表偏差目标值252.5155.75-38.17%工资成本575522-9.22%班次满意度71594331.19%运行时间/11.29s/仿真目标值 手工目标值其中，目标值偏差手工目标值*100% 。工资成本和班次满意度的偏差类似计算。从表5-6 可见，护士排班模型的目标值比实际手工排班的目标值低38.17%，其中护士工资成本降低9.22%，但是护士对班次的满意度提升了 31.19%。这表明 :基于强、弱约束的护士排班模型明显优于手工排班模式，并且医院管理成本和护士对工作的满意度得到了有效的改善。5.3 模拟退火算法仿真结果在 MATLAB 上用模拟

27、退火算法对护士排班模型 (2.2.14)进行仿真，采用近邻编码，取初始状态 t0 =10001，退温策略选用指数倒退函数，即 tk= tk-1，退温速率 =0.99，迭代终止策略为连续 20 代不变。如此的算法收敛情况如图 5.1 所示，所得结果如表 5-7 所示。图 5.1 SA 算法收敛图表 5-7 护士排班模型计算结果手工排班表仿真排班表偏差目标值252.5143-43.4%工资成本575513-10.8%班次满意度71596735.24%运行时间/5.08s/从表 5-7 可知，护士排班模型的目标值比实际手工排班的目标值降低了43.43%，其中工资成本降低 10. 8%，但是护士对班次

28、的满意度却提升了 3 5.24%。这表明 :基于强、弱约束的护士排班模型明显优于手工排班模式， 在医院工资成本控制和护士的满意度提升方面达到了有效的平衡，而基于模拟退火算法的成功应用护士排班模型，对求解大规模的护士排班问题带来新的启发和思路。5.4 分支界定与模拟退火算法混合仿真结果参数选择与 SA 仿真相同。混合算法结果如表5-8 所示，收敛情况如图5.2 所示。图 5.2 SA 算法收敛图表 5-8 护士排班模型计算结果手工排班表仿真排班表偏差目标值252.5133-47.32%工资成本575504-10.96%班次满意度71598037.6%运行时间/8.76s/基于分支定界和模拟退火算

29、法的混合优化策略求得目标值比手工排班低47.32%，其中工资成本下降 10.96%，而护士工作班次满意度上升 37.6%。这表明 :基于分支定界和模拟退火算法的混合优化策略明显强于原始的排班表， 在护士排班模型的求解中能取得好的效果。6 结论（1）基于分支定界和模拟退火算法的混合优化策略融合了分支定界和模拟退火算法优化机制融合、算法结构互补、优化操作的结合、优化行为的互补和削弱参数的苛刻条件等优点，综合评价最好，其护士排班模型的优化性能和算法的效率远远好于传统的数学规划和单一的启发式算法。（ 2)基于强、弱约束的护士排班模型明显优于手工排班模式，并且医院管理成本和护士对工作的满意度得到了有效的

30、改善。 其中增加的 “APN 排班”机制能有效的应付高峰时段护理压力和错开上下班的交通高峰期 ;更多的护士在周末可以休息将有效改善护士的家庭关系，而排班的公平性护士，提高护士的身心健康，使得整个医院的护理工作更加高效的开展和管理。参考文献1刘玉宽，张莉，李梅. 医疗卫生机构陷入困境的原因和出路fJ.中国卫生经济，1999,18(6):15一 162 丰雪荣，华正丽. 护士的压力源分析及应对措施J. 中国医药指南，2011,9(33):153-1543 范淑玉等 . 我国护士排班状况研究进展 J. 护士管理杂志， 2008,8(12):27-294 姜小鹰 . 护理管理学 M. 上海 : 上海科

31、学技术出版社， 2001:139-1435BelienJ,Demeulem eesterE. A Branchand Price Approachfor IntegratingNurseandSurgery Scheduling J. European Journal of Operational Research, 2008,189(3): 652-6686AickelfinU, Li J.An Estimationof DistributionAlgorithm forNurse7 Bard J E Pu rnomo H W Cyclic Preference Scheduling of

32、Nurses Using a Lag rangianBased Heuristic J. Journal of Scheduling, 2007, 10(1): 5-238Holmes E.Miller,WilliamP. Pierskalla,etal.Nurse SchedulingUsingMathematicalProgramming J. Operations Research, 1976, 24(5):857一 8709D.M.Warner.Schedulingnursingpersonnelaccordingtonursingpreference: Amathematicalpr

33、ogrammingapproachJ.OperationsResearch, 1976,24(5):842-85610 B.Jaumard, F. Semet, and T.Vovor .A generalized linear programming model for nursescheduling J.European Journal of Operational Research, 1998, 107(1):1 一 1811 Ozkarahan, J. E. Bailey. Goal programming model subsystem of a flexiblenurseschedulingsupportsystemJ.IIETransactionsonIndustrialElectronics,2003, 50(3):833一 83812M aenhout B, Uanh oucke M. Comparisonand HybridizationofCrossoverOperatorsfortheNurse SchedulingProblemJ.Annals of OperationsResearch,2008, 159(1):333 一 35313BurkEK,CurtoisT,Postqet