护士排班问题标准管理系统建模与优化作业.docx

管理系统建模和优化期末作业护士排班问题专业：管理科学和工程时间：1月目录1 案例背景22 研究现实状况23 案例模型23.1 护士排班问题23.2 护士排班模型24 护士排班算法24.1 整数计划24.2 模拟退火算法24.3 整数计划和模拟退火混合算法25 案例计算和分析25.1 案例数据25.2 分支界定法计算结果25.3 模拟退火算法仿真结果25.4 分支界定和模拟退火算法混合仿真结果26 结论2参考文件2护士排班问题1 案例背景护理工作是整个医疗卫生工作关键组成部分，在医疗实践中担负着特殊工作和任务，是整个医院开展医疗服务运行基础。现在各国护士短缺严重，已引发了国外护理管理高度重视1。中国护士长久处于特殊环境气氛和接待多种病情患者，并承受超负荷工作和长久担心脑力劳动、不规则排班等护理情况，它将直接影响护士身心健康，影响工作质量，造成护患关系担心2。科学管理护理资源，有效控制医院护理成本预算和提升患者满意度是现在研究热点课题3。在现在护理工作量大、应急性险强、不规则轮班，传统单一简单排班模式情况下，因为医院存在控制成本压力，造成了医院和护士利益冲突和目标差异，为愈加好调高护理质量、降低医院护理成本，需要建立一个完整带有劳动法规约束和满足护士本身需求护士排班模型和护士排班算法。护士排班问题关键是指在现有医疗资源约束条件下，从医院护理成本、护士满意度、班次偏好、降低护士工作压力和改善护士身心健康等方面，编制出科学排班表，从而有效改善排班表质量和提升护理工作满意度和社会形象42 研究现实状况国外对护士排班问题研究起步较早，护士排班问题已经被临床研究机构和计算机方面研究多达40余年了，护士排班问题是建立在一系列劳动法规和班次需求约束下复杂组合优化问题，属于NP问题5,6,7，现在可行关键技术是数学计划8,9,10,11,12和启发式算法13,14,15和传统数学计划和启发式算法融合技术，不过国外劳动法规和护士工作情况和中国完全不一样，模型和约束条件和中国存在显著差异。而中国护士排班问题研究起步较晚，关键是按功效模式和整体护理模式排班，按固定、弹性、“三班制”、APN”排班，护士自我排班等简单手工排班模式16，而定量排班ILP模型约束条件并未考虑“APN”等机制和排班公平性等，难以综合考虑以病人需要为中心、互补增值、均衡平等、稳定机制、人性化标准，故缺乏一套有效模型优化机制。因为一系列约束条件和护士偏好,整个护士排班模型是复杂组合优化问题,比TSP问题更难NP问题,处理此问题能有效推进调度算法改善。伴随现代医院发展,医院资源资源紧缺和护士短缺和护士本身潜在需求,迫切需要实现信息化护士排班系统,从而有效改善护士管理和工作情况,整合医院资源优势,愈加好为患者服务,有效改善医患关系,促进社会友好发展。3 案例模型3.1 护士排班问题护士排班问题是一个满足系列劳动法规和班次约束护理资源最优分配问题。在实际护士排班中，约束条件关键包含工作强度要求、夜班班次要求、护士对工作环境满意度、工作时段偏好和排班公平性等。护士排班问题目标就是在一个排班周期内(一周或一月)，满足一系列劳动约束和医院资源需求约束，使得整个医院护理成本最小化和护士工作满意度最高。护士排班问题要服从以下三个关键假设:（1）护士排班模型约束条件必需符合中国现行劳动法规和大型医院护理工作实际情况。（2）护士本身要求要尽可能去满足，这对于护士排班问题研究是很关键。（3）没有必需把在岗全部护士全部考虑在护士排班模型之中。那些实习和兼职护士能够实施排班后，依据实际情况动态调整到护士排班表中。自从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 Constraint,HC)是在中国任何医院护士排班环境中全部必需满足约束条件，不然整个排班表就不可行。强约束条件关键考虑劳动法规、医院护理资源和班次约束等:HC1: A班和P班全部有1-2名中级资质以上护士;HC2: 任何一个班次(A班、P班和N班)护士数不低于实际需求量;HC3: 每位护士一天最多只能进行一个班次工作;HC4: 任何护士在相邻2天班次不能连续(若第1天排N班，则第2天不能排A班);HCS: 在一个排班周期内，每位护士最长工作班次不能超出要求上限;HC6: 在一个排班周期内，每位护士最短工作班次不能少于要求下限;HC7: 在一个排班周期内，每位护士最长连续N班不能超出要求上限;HC8: 在一个排班周期内，每位护士最长连续班次不能超出要求上限;弱约束条件(Soft Constraint, SC)是指在医院实际护士排班中尽可能多去满足条件，各所医院在实际排班巾将弱约束条件进行调整和增加，本文中关键考虑护士周末休息和排班公平性:SC1:尽可能多护士在周末最少休息一天;SC2:不对某个护士特殊照料A班;假如护士排班表满足了全部强、弱约束条件，则为可行护士排班表，如表3-1所表示:表3-1 可行护士排班表周一周二周三周四周五周六周日1AAPRNNR2RANNRPNNPNNRAAR3.2 护士排班模型护士排班模型目标就是在一个排班周期内(一周或一月)，满足一系列劳动法规、医院护理资源需求和班次约束条件下，使得整个医院护理成本最小化和护士工作满意度最高。意在降低医院护理运行成本，同时有效降低护士工作压力，让护士愈加好处理好工作、生活和家庭关系、从而提升医院护理工作效率。参数假设:I=1,2,n 表示n名护士集合;T=1,2,J 表示一个排班周期内天数集合;K=1,2,3,4 表示天天班次类型(A,P,N,R);m表示在一个排班周期内，每位护士最长工作时间;w表示在一个排班周期内，每位护士最短工作时间;n1表示在一个排班周期内，每位护士连续夜班最长时间;n2表示在一个排班周期内，每位护士连续班次最长时间;cijk表示第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; qi=1, 中级及以上职称0， 其它 1表示工资成本权重系数，其中凡10,1;2表示班次满意度权重系数，其中20,1;基于上述定义参数，我们建立以下护士排班模型:min F(x)=f1x,f2(x) (3-1)其中f1x=i=1nj=1Jk=14cijkxijk (3-2)f2x=i=1nj=1Jk=14pikxijk (3-3)s.t. HC1:1i=1nqixij12 , 1i=1nqixij22 iI, jT (3-4)HC2:i=1nxijkdjk jT, k1,2,3 (3-5) HC3:k=14xijk=1 iI, jT (3-6)HC4:xij3+xi(j+1)11 iI, jT (3-7)HC5:j=1Jk=13xijkm iI (3-8)HC6:j=1Jk=13xijkw iI (3-9)HC7:j=rr+n1xij3n1 iI, r1,2,J-n1 (3-10)HC8:j=rr+n2k=13xijkn2 iI, r1,2,J-n1 (3-11)SC1:xij4+xi(j+1)41 i1,2,10, jT (3-12)SC2:x23j1=0 jT (3-13)护士排班模型要求在任何排班中强约束条件全部必需满足，并尽可能多满足弱约束条件。可依据实际环境中关键性程度将弱约束做出以下次序:SC1 SC2，其中“”表示优先级，优先级次序由医院决定。由此可将目标函数(3-1)化为:min F(x)=i=12ifi(x) , 其中 i=12i=1 (3-14)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, ILP)是最优化理论中比较关键体系，在工业和工程设计和科学研究方面、计算机设计、系统可靠性、编码和经济分析等很多领域有广泛应用。不过整数线性计划问题属于NP难问题，通常不存在多项式算法，现在求解ILP方法关键有分支定界法、割平面法、多面体法、列生成法、禁忌搜索和遗传算法等53,54,55。在求解整数线性计划问题中，分支定界算法是一个最常见方法，分支定界(branch and bound)算法在问题解空间上采取树形搜索整数计划问题方法。分支定界(branch and bound)算法是一个在问题解空间树上搜索问题解方法。但和回溯算法不一样，分支定界算法采取广度优先或最小花费优先方法在解空间搜索树，而且在分支定界算法中，每一个活结点只有一次机会成为扩展结点。对于大规模整数计划问题(IP，直接采取举例法相当困难，采取“分而治之”（divide and conquer）策略，先将可行解区域划分为部分小解集合，然后在较小解集合上求解对应目标函数最优值，并将所求结果集成在一起生成原问题最优解。在求解较小解集合对应子问题时，既能够采取分而治之策略进行分析，也能够采取其方法对子问题进行求解。分支定界算法基础思想是从原问题(IP)线性计划松弛解X出发，若最优解不符合原问题整数条件，那么该解X必是原问题上界z，而原问题任何可行解全部看作是目标解一个下界z。它将可行解区域划分为若干子区域，并逐步缩小上界z和增大下界z，从而得到最优目标解z*，以求得最优解。对于0-1整数计划问题分支定界算法步骤以下所表示:0-I整数计划问题分支界定算法步骤58步骤1(初始):求解原问题(IP)线性计划松弛解，若得到整数解，则视为原问题最优解，不然得到原问题一个上界;步骤2(分支):选择合适变量xi，分别固定xi =0和xi =1得到2个子问题;步骤3(定界):选择一个子问题，求解该子问题线性计划松弛解;步骤4(剪枝):若发生下列情况之一，则停止对该问题进行分支(剪枝):（1）子问题线性计划松弛解最优解是整数;（2）子问题不可行;（3）子问题上界等于或小于已知可行解目标函数值。步骤5(最优性):反复上述过程，直到分支定界树中没有需要考虑节点(子问题)，则目前最好可行解就是原问题(IP)最优解.4.2 模拟退火算法组合优化(Combinatorial Optimization)问题目标就是从组合问题可行解空间求出最优解，通常包含变量、约束和目标函数这三个基础要素。在求解过程中选定基础参数称为变量，对变量取值种种限制称为约束，表示可行方案衡量标准函数称为目标函数。求解组合优化问题就是在目标函数解集合里找到最适合解，这肯定要求利用一定算法去降低求解过程时间复杂性和空间复杂性。Kirkpatrick等在1982年结合固体退火过程状态改变思想，提出一个类似固体退温过程有效近似算法一模拟退火算法(Simulate Anneal，简称SA)，以处理大规模组合优化问题碰到瓶颈。模拟退火算法58, 59, 60是处理组合优化问题算法，它采取Metropolis接收准则使算法跳离局部“最优”陷阱，并使用“冷却进度表”来控制整个算法实施过程，最终使算法能够在多项式时间内得出一个近似最优解。一个优化问题能够描述为:其中S是一个离散有限状态空间，i代表状态。针对这么一个优化问题，SA算法计算步骤能够描述以下:min f(i), iS 第1步:初始化，任选初始解iS，给定初始温度T0和终止温度Tf，令迭代指标k=0，Tk=T0。第2步:随机产生一个领域解jNi，（Ni表示i领域），计算目标值增量f=fj-f(i)。第3步:若f，则令i=j。第4步:若达成热平衡(内循环次数大于n（Tk)转第5步；不然转第2步。第5步:降低Tk，k=k+1，若Tk Tf，则算法停止，不然转第2步。上述模拟退火算法步骤图4.1所表示。图4.1 SA算法步骤图4.3 整数计划和模拟退火混合算法在护士排班领域研究中，部分算法混合优化技术已经存在很多年了。国外将整数计划和领域搜索算法混合优化策略应用于护士排班领域，有效改善了解质量和算法效率。基于上述研究，本文提出整数计划和模拟退火算法混合优化策略处理护士排班问题约束条件和护士潜在要求，从算法优化机制融合、算法结构互补、优化操作结合、优化行为互补和减弱参数苛刻条件等方面61叙述了混合优化机制优越性，其中整数计划分支定界算法确保了解可行解，而模拟退火算法以一定概率接收劣解，从而有效扩大可行解区域，能高效求解组合优化问题。分支定界算法(BBA)和模拟退火算法(SA)混合策略，以下简称BBASA, BBASA算法其算法步骤以下:步骤1:状态初始化，确定初温;步骤2:确定最大点，次大点，最小点;步骤3:算法收敛准则是否满足，满足就输出结果;不然转到步骤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, 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换班合理性如护士上了晚班以后应该安排休息，不能又安排 护士继续去上早班8排班周期内上班工时平衡要确保在排班周期内每个护士工时相等9排班周期内上晚班平衡要确保在排班周期内每个护士上晚班次数相对公平10排班周期内休息时间平衡要确保在排班周期内每个护士休息时间相对公平11排班周期内班次平衡要确保在排班周期内每个护士上多种班次次数相对公平12排班高规律性护士上班时间改变相对稳定，不要天天变动全部很大，提供一个人性化排班由上述排班质量影响原因统计表可知，每位护士可连续工作最长时间是4个班次，可连续夜班最长时间是2个班次。在一个排班周期内内每位护士最长工作班次至多为6个班次，最短工作班次最少为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 护士原始排班表序号周一周二周三周四周五周六周日1APRNNAP2APPRAPN3PANRAPA4APNRAAP5PRPRAAP6RRPAPNN7APPRPNN8APPRPAP9PRNNRPA10PRNNRPP11PAARPNR12PAPNPPN13PRAPARN14PRANNRP15NNRAPAP16RNRRPNP17NNRAPAN18NNRPNRA19RPAPRPA20RPAPNRA21RAAPPRP22RAPNRAP23NRPARPA24RPAARNP25RPRPNNN26RNNRRPP27NNRPAPN28RNNRAPP29RAAPRPP30RPPANRA因为每位护士在不一样班次内工资成本是不一样，定义工资成本为5个等级，5代表最高等级工资，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初233123中344224初233125高455326高455327中344228初233129中344230初2331每位护士对各个班次工作满意度是不一样，定义班次满意度为5个等级，1=很不满意，2=不满意，3二通常，4=满意，5=很满意，为了计算统一性，将对R班定义为很满意，具体班次满意度表见下表5-5所表示表5-5 护士班次满意度序号APNR1532525325325154251555215625157251585215925151025151152151252151312551425151525151625151725151812551925152025152112552212552352152425152512552612552753252853252925153025155.2 分支界定法计算结果 在MATLAB上用分支界定算法对护士排班模型进行仿真试验，并令1=0.75，2=0.25，其计算结果如表5-6所表示。表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上用模拟退火算法对护士排班模型(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%，不过护士对班次满意度却提升了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/基于分支定界和模拟退火算法混合优化策略求得目标值比手工排班低47.32%，其中工资成本下降10.96%，而护士工作班次满意度上升37.6%。这表明:基于分支定界和模拟退火算法混合优化策略显著强于原始排班表，在护士排班模型求解中能取得好效果。6 结论（1）基于分支定界和模拟退火算法混合优化策略融合了分支定界和模拟退火算法优化机制融合、算法结构互补、优化操作结合、优化行为互补和减弱参数苛刻条件等优点，综合评价最好，其护士排班模型优化性能和算法效率远远好于传统数学计划和单一启发式算法。（2)基于强、弱约束护士排班模型显著优于手工排班模式，而且医院管理成本和护士对工作满意度得到了有效改善。其中增加“APN排班”机制能有效应付高峰时段护理压力和错开上下班交通高峰期;更多护士在周末能够休息将有效改善护士家庭关系，而排班公平性护士，提升护士身心健康，使得整个医院护理工作愈加高效开展和管理。参考文件1 刘玉宽，张莉，李梅.医疗卫生机构陷入困境原因和出路fJ.中国卫生经济，1999,18(6):15一162 丰雪荣，华正丽.护士压力源分析及应对方法J.中国医药指南，,9(33):153-1543 范淑玉等.中国护士排班情况研究进展J.护士管理杂志，,8(12):27-294 姜小鹰.护理管理学M.上海:上海科学技术出版社，:139-1435 Belien J, Demeulem eester E. A Branch and Price Approach for Integrating Nurse andSurgery Scheduling J. European Journal of Operational Research, , 189(3): 652-6686 Aick elfin U, Li J. An Estimation of Distribution Algorithm for Nurse Scheduling J.Annals of Operations Research, , 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, , 10(1): 5-238 Holmes E.Miller, William P. Pierskalla, 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 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 flexible nursescheduling support system J.IIE Transactions on Industrial Electronics, , 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, , 159(1): 333一35313 Burk EK, Curtois T, Post q et al. A Hybrid Heuristic Ordering and VariableNeighborhood Search f or the Nurse Rostering Problem J. European Journal of Operat Tonal Research, , 188(2): 330-34114 Tsai C C, LiSHA. A Two Stage Modeling with Genetic Algorithms for the NurseScheduling Problem J. Expert Systems with Applications, , 36(5): 9506 -951215 Aickelin U, Burk e E K, Li J. An Estimation of Distribution Algorithm with IntelligentLocal Search for Rule Based Nurse Rostering J. Journal of the Operational Research Society, , 58(12): 1574一158516 刘梅，廖少玲，文若兰.护士排班研究现实状况J.广东医学院学报，,29(2):210-21217 Hanif D. Sherali, Patrick J.Driscoll. Evolution and state-of-the-art in integer programmingJ. Journal of Computational and Applied Mathematics，,124(1-2):319-34018 ELLIS L. JOHNSON, GEORGE L. NEMHAUSER, MARTIN W.P. Progress in LinearProgramming-Based Algorithms for Integer Programming: An Exposition J. Journal onComputing, , 12(1):2-2319 Tobias Achterberga, Thorsten Kocha. Alexander Martinb. Branching rules revisited J.Operations Research Letters, , 33(1):42一5420 康立山，谢云，尤矢勇等.非数值并行算法(第一册升模拟退火算法M.北京:科学出版社，1994, 22-12521 王凌.智能优化算法及其应用M.北京:清华大学出版社/施普林格出版，,130-141