护士排班问题——管理系统建模与优化作业

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班。其中“APN”充分保证了高峰时段的护理安全。强约束条件(Hard Co

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

8、过规定的上限；HC8:在一个排班周期内，每位护士的最长连续班次不能超过规定的上限；弱约束条件(Soft Constraint, SC)是指在医院实际护士排班中尽可能多的去满足的 条件，各所医院在实际排班巾将弱约束条件进行调整和增加，本文中主要考虑护士的周 末休息和排班的公平性：SC1:尽可能多的护士在周末至少休息一天;SC2:不对某个护士特殊照顾A班；如果护士的排班表满足了所有的强、弱约束条件，则为可行的护士排班表，如表3-1所示：表3-1可行护士排班表1周二周三周四周五周六1AAPRNNR2RANNRPNNPNNRAAR3.2护士排班模型护士排班模型的目标就是在一个排班周期内(一周或一月)，

9、满足一系列劳动法规、医院护理资源需求和班次约束条件下，使得整个医院的护理成本最小化和护士工作的满意度最高。旨在降低医院的护理运营成本，同时有效降低护士工作压力，让护士更好的处理好工作、生活和家庭的关系、从而提高医院的护理工作效率。参数假设:表示 n 名护士集合;表示一个排班周期内的天数集合;表示每天班次的类型（A,P,N,R）;m 表示在一个排班周期内，每位护士的最长工作时间;w 表示在一个排班周期内，每位护士的最短工作时间;n1 表示在一个排班周期内，每位护士连续夜班的最长时间;n2表示在一个排班周期内，每位护士连续班次的最长时间；5k表示第i位护士在第j天选择第k个班次工作的工资等级，记为

10、Cjk=1,2,3,4,5;djk 表示在第j 天第 k 班次对护士的需求量;pik 表示第 i 位护士对第k 个班次的工作满意度，记为pik=1（ 非常不满意）,2（不满意）， 3（一般）,4（满意）， 5（非常满意）;xijk=1表示第i位护士在第J天安排第k个班次，反之xijk=0；中级及以上职称，其他入i表示工资成本权重系数，其中凡 入i 0,1；入2表示班次满意度权重系数，其中 入2 0,1;基于上述定义的参数，我们建立如下护士排班模型:其中s.t. HC1:HC2:HC3:HC4:HC5:HC6:HC7:HC8:SC1:SC2:护士排班模型要求在任何排班中强约束条件都必须满足，并尽

11、可能多的满足弱约束条件。 可根据实际环境中的重要性程度将弱约束做出如下的顺序: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 位护士排班，并假设每日分 4 个班次，故模型的求解难度与护士数量呈线性关系。4护士排班算法4.1 整数规划整数线性规划(Integer Linear Programming,

12、ILP)是最优化理论中比较重要的体系， 在工业和工程设计和科学研究方面、计算机设计、系统可靠性、编码和经济分析等诸多 领域有广泛应用。但是整数线性规划问题属于NP难问题，一般不存在多项式算法，目前求解ILP的方法主要有分支定界法、割平面法、多面体法、列生成法、禁忌搜索和遗 传算法等53,54,55。在求解整数线性规划问题中，分支定界算法是一种最常用的方法， 分支定界(branch and bound)算法在问题的解空间上采取树形搜索整数规划问题的方 法。分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法。 但与回溯算法不同，分支定界算法采用广度优先或最小

13、耗费优先的方法在解空间搜索树， 并且在分支定界算法中，每一个活结点只有一次机会成为扩展结点。对于大规模整数规 划问题(IP ,直接采取举例法相当的困难，采用“分而治之"(divide and conquer )的策略，先将可行解区域划分为一些小的解集合，然后在较小的解集合上求解相应目标函 数的最优值，并将所求结果集成在一起生成原问题的最优解。在求解较小的解集合对应 的子问题时，既可以采用分而治之的策略进行分析，也可以采取其方法对子问题进行求 解。分支定界算法的基本思想是从原问题(IP)的线性规划松弛解X出发，若最优解不符 合原问题的整数条件，那么该解 X必是原问题的上界，而原问题的任

14、何可行解都看作 是目标解的一个下界_0它将可行解区域划分为若干子区域，并逐步缩小上界和增大下. . . . . . . - - * . 一 一-界一从而得到最优目标解z ,以求得最优解。对于0-1整数规划问题的分支定界算法步骤如下所示：0-I整数规划问题分支界定算法流程58步骤1(初始)：求解原问题(IP)的线性规划松弛解，若得到整数解，则视为原问题的 最优解，否则得到原问题的一个上界；步骤2(分支)：选择适当的变量Xi,分别固定Xi =0和Xi =1得到2个子问题；步骤3(定界)：选择一个子问题，求解该子问题的线性规划松弛解；步骤4(剪枝)：若发生下列情况之一，则停止对该问题进行分支(剪枝)

15、：(1)子问题的线性规划松弛解的最优解是整数；(2)子问题不可行；(3)子问题的上界等于或小于已知的可行解的目标函数值。步骤5(最优性)：重复上述过程，直到分支定界树中没有需要考虑的节点(子问题)，则当前最好的可行解就是原问题(IP)的最优解.4.2 模拟退火算法组合优化(Combinatorial Optimization)问题的目标就是从组合问题的可行解空间求出最优解，一般包含变量、约束和目标函数这三个基本要素。在求解过程中选定的基 本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为 目标函数。求解组合优化问题就是在目的函数的解集合里找到最适合的解，这必然要求 运

16、用一定的算法去降低求解过程的时间复杂性和空间复杂性。Kirkpatrick 等在1982年结合固体退火过程状态变化的思想，提出一种类似固体退温过程的有效近似算法一模 拟退火算法(Simulate Anneal ,简称SA),以解决大规模组合优化问题遇到的瓶颈。模 拟退火算法58, 59, 60是解决组合优化问题的算法，它采用 Metropolis接受准则使 算法跳离局部“最优”的陷阱，并使用“冷却进度表”来控制整个算法实施过程，最终使算法能够在多项式时间内得出一个近似最优解。一个优化问题可以描述为：其中S是一个离散有限状态空间，i代表状态。针对这样 一个优化问题，SA算法的计算步骤能够描述如下

17、：第1步：初始化，任选初始解，给定初始温度T0和终止温度Tf,令迭代指标k=0,Tk=To。第2步：随机产生一个领域解表示 的领域），计算目标值增量第3步：若令 i=j 。图4.1 SA算法流程图，令i=j转第4步；否则产生随机量±二U（0,1）,若第4步：若达到热平衡（内循环次数大于n （Tk）转第5步；否则转第2步。第5步：降低Tk, k=k+1,若Tk < Tf,则算法停止，否则转第2步。上述模拟退火算法流程如图4.1所示。4.3 整数规划与模拟退火混合算法在护士排班领域研究中，一些算法的混合优化技术已经存在很多年了。国外将整数 规划和领域搜索算法的混合优化策略应用于护士

18、排班领域，有效的改善了解的质量和算法的效率。基于上述的研究，本文提出整数规划和模拟退火算法混合优化策略处理护士 排班问题的约束条件和护士的潜在要求，从算法的优化机制融合、算法结构互补、优化 操作的结合、优化行为的互补和削弱参数的苛刻条件等方面61阐述了混合优化机制的 优越性，其中整数规划的分支定界算法保证了解的可行解，而模拟退火算法以一定的概 率接受劣解，从而有效扩大可行解区域，能高效求解组合优化问题。分支定界算法（BBA）与模拟退火算法（SA）的混合策略，以下简称BBASA, BBASA算 法其算法流程如下：步骤1:状态初始化，确定初温；步骤2:确定最大点，次大点，最小点；步骤3:算法收敛准

19、则是否满足，满足就输出结果；否则转到步骤4;步骤4:使用分支定界算法求出局部极小点：步骤5:由SA利用“护士互换规则”和“班次调整规则”规则产生函数产生新个体步骤6:以一定概率接受新个体；步骤7: SA抽样稳定，则进行退温操作，跳到步骤 3;否则返回步骤5;步骤8:退出上述模拟退火算法流程如图4.2所示。图4.2 BBASA算法流程图5案例计算与分析5.1案例数据本文的护士数据来源于XX医院护士工作状况调研问卷的调研结果。目前某三 甲医院重症科室共有30名护士，其中高、中、初级护士分别 3, 5和22位。假设排班周 期为一周（J=7）,并将每天的工作时间平均分为 a班（8:00-16:00,

20、p班（6:00-0:00）和N班 （0:00-8:00）三种班次。影响排班质量的主要因素如表 5-1所示。表5-1排班质量影响因素表序号123456排班影响因素 连续上班天数 连续工作时长 连续晚班时长排班周期内的总班次排班周期内的总工时连续休息天数换班的合理性8910排班周期内上班工时的平衡排班周期内上晚班的平衡排班周期内休息时间的平衡11排班周期内班次的平衡12排班的高规律性参考建议3-4天3-10小时1-2天4-6天周工时在40小时左右1-2天如护士上了晚班之后应该安排休息，不能又安排护士继续去上早班要保证在排班周期内每个护士的工时相等要保证在排班周期内每个护士上晚班的次数相对公平要保证

21、在排班周期内每个护士休息的时间相对公平要保证在排班周期内每个护士上的各种班次的次数相对公平护士上班的时间变化相对稳定，不要每天的变动都很大，提供一种人性化的排班由上述排班质量影响因素统计表可知，每位护士可连续工作的最长时间是 4个班次, 可连续夜班的最长时间是2个班次。在一个排班周期内内每位护士最长工作班次至多为6个班次，最短工作班次至少为 4个班次，在排班周期内的总工时大概在 40小时左右, 而每天“APN”各班次的实际需求护士数目由科室护士长给定，如表5-2所示：表5-2各班次护士需求人数（A/P/N）1周二周三周四周五周六周日9/6/48/5/39/6/38/5/39/7/410/7/7

22、10/7/7XX医院重症科室采取的是“弹性排班”制，每周的排班表由护士长根据科室的护 士需求量和护士的家庭、生活状态等约束手工排班而成，详细的手工排班表如下表5-3所示。表5-3护士原始排班表序号周二周三周四周五周六周日1APRNNAP2APPRAPN3PANRAPA4APNRAAP5PRPRAAP6RRPAPNN7APPRPNN8APPRPAP9PRNNRPA10PRNNRPP11PAARPNR12PApNPPN13PRAPARN14PRANNRP15NNRAPAP16RNRRPNP17NNRAPAN18NNRPNRA19RPAPRPA20RPAPNRA21RAAPPRP22RAPNRAP2

23、3NRPARPA24RPAARNP25RPRPNNN26RNNRRPP27NNRPAPN28RNNRAPP29RAAPRPP30RPPANRA5个等级，51止乂，贸以小力代表最高级别的工资，1代表最低级别的工资，30位护士的工资级别如下表5-4所示:表5-4护士工资表序号职称APNR1中34422初23313中34424初23315初45536中34427初23318初23319初233110初233111初233112初233113初233114初233115初233116中344217初233118初233119初233120初233121初233122初2331231344224初233

24、125高455326高455327中344228初233129中344230初2331每位护士对各个班次的工作满意度是不一样的， 定义班次满意度为5个级别，1=非 常不满意，2=不满意，3二一股，4=满意，5=非常满意，为了计算的统一性，将对 R班定义为非常满意，详细的班次满意度表见下表5-5所示表5-5护士班次满意度序号APNR15325253253251542515552156251572515852159251510251511521512521513125514251515251516251517251518125519251520251521125522125523521524251

25、52512552612552753252853252925153025155.2 分支界定法计算结果在MATLAB上用分支界定算法对护士排班模型进行仿真实验，并令 入1=0.75,入 2=0.25,其计算结果如表5-6所示。表5-6护士排班模型计算结果手工排班表仿真排班表Bit目标值252.5155.75-38.17%工资成本575522-9.22%班次满意度71594331.19%运行时间/11.29s/其中，目标值偏差44 ”00%。工资成本和班次满意度的偏差类似计算。从表5-6可见，护士排班模型的目标值比实际手工排班的目标值低38.17%,其中护士工资成本降低9.22%,但是护士对班次的

26、满 意度提升了 31.19%。这表明：基于强、弱约束的护士排班模型明显优于手工排班模式， 并且医院管理成本和护士对工作的满意度得到了有效的改善。5.3 模拟退火算法仿真结果在MATLAB上用模拟退火算法对护士排班模型（2.2.14）进行仿真，采用近邻编码， 取初始状态t0=10001,退温策略选用指数倒退函数，即tk= X tk-1,退温速率入=0.99,迭 代终止策略为连续20代不变。如此的算法收敛情况如图5.1所示，所得结果如表5-7所 示。图5.1 SA算法收敛图表5-7护士排班模型计算结果手工排班表仿真排班表目标值252.5143-43.4%工资成本575513-10.8%班次满意度7

27、1596735.24%运行时间/5.08s/从表5-7可知，护士排班模型的目标值比实际手工排班的目标值降低了43.43%,其中工资成本降低10. 8%,但是护士对班次的满意度却提升了 3 5.24%。这表明：基于强、 弱约束的护士排班模型明显优于手工排班模式，在医院工资成本控制和护士的满意度提 升方面达到了有效的平衡，而基于模拟退火算法的成功应用护士排班模型，对求解大规 模的护士排班问题带来新的启发和思路。5.4 分支界定与模拟退火算法混合仿真结果参数选择与SA仿真相同。混合算法结果如表 5-8所示，收敛情况如图5.2所示。图5.2 SA算法收敛图表5-8护士排班模型计算结果手工排班表仿真排班

28、表目标值252.5133-47.32%工资成本575504-10.96%班次满意度71598037.6%运行时间/8.76s/基于分支定界和模拟退火算法的混合优化策略求得目标值比手工排班低47.32%,其中工资成本下降10.96%,而护士工作班次满意度上升 37.6%。这表明：基于分支定界和 模拟退火算法的混合优化策略明显强于原始的排班表，在护士排班模型的求解中能取得好的效果。6 结论（ 1）基于分支定界和模拟退火算法的混合优化策略融合了分支定界和模拟退火算法优化机制融合、算法结构互补、优化操作的结合、优化行为的互补和削弱参数的苛刻条件等优点，综合评价最好，其护士排班模型的优化性能和算法的效率

29、远远好于传统的数学规划和单一的启发式算法。（ 2）基于强、弱约束的护士排班模型明显优于手工排班模式，并且医院管理成本和护士对工作的满意度得到了有效的改善。其中增加的“ APN 排班” 机制能有效的应付高峰时段护理压力和错开上下班的交通高峰期;更多的护士在周末可以休息将有效改善护士的家庭关系，而排班的公平性护士，提高护士的身心健康，使得整个医院的护理工作更加高效的开展和管理。参考文献1 刘玉宽，张莉，李梅. 医疗卫生机构陷入困境的原因和出路fJ. 中国卫生经济，1999,18(6):15 一 162 丰 雪 荣 ， 华 正 丽 . 护 士 的 压 力 源 分 析 及 应 对 措 施 J. 中 国

30、 医 药 指 南 ， 2011,9(33):153-1543 范淑玉等. 我国护士排班状况研究进展J. 护士管理杂志，2008,8(12):27-294 姜小鹰 . 护理管理学M. 上海 : 上海科学技术出版社，2001:139-1435 Belien J, Demeulem eester E. A Branch and Price Approach for Integrating Nurse andSurgery Scheduling J. European Journal of Operational Research, 2008, 189(3): 652-6686 Aick elfin

31、U, Li J. An Estimation of Distribution Algorithm for Nurse Scheduling J.Annals of Operations Research, 2007, 155(1): 289 -3097 Bard J E Pu rnomo H W Cyclic Preference Scheduling of Nurses Using a Lag rangianBased Heuristic J. Journal of Scheduling, 2007, 10(1): 5-238 Holmes E.Miller, William P. Pier

32、skalla, et al. Nurse Scheduling Using MathematicalProgramming J. Operations Research, 1976, 24(5):857一 8709 D.M.Warner. Scheduling nursing personnel according to nursing preference: Amathematical programming approach J. Operations Research, 1976, 24(5):842-85610 B.Jaumard, F. Semet, and T.Vovor .A g

33、eneralized 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 flexible nursescheduling support system J.IIE Transactions on Industrial Electronics, 2003, 50(3):833 一 83812 M aenhout B, Uanh oucke M. Comparison and Hybridization of Crossover Operators forthe Nurse Scheduling Problem J. Annals of Operations Research, 2008, 159(1): 333 一 35313 Burk EK, Curtois T, Post q et al. A Hybrid Heuristic Ordering and VariableNeighb