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

1、管理系统建模与优化期末作业护士排班问题专业：管理科学与工程时间：2015年1月目录1案例背景32研究现状33案例模型43.1 护士排班问题43.2 护士排班模型44护士排班算法74.1 整数规划74.2 模拟退火算法74.3 数规划与模拟退火混合算法85案例计算与分析105.1 案例数据105.2 分支界定法计算结果125.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）护士排班模型的约束条件必须符合我国现行的劳动法规和大型医院护理工作实际状况。（2）护士的自身的要求要尽量去满足，这对于护士排班问题的研究是很重

6、要的。（3）没有必要把在岗的所有护士都考虑在护士排班模型之中。那些实习和兼职的护土可以实行排班后，根据实际情况动态调整到护士排班表中。自从2008年5月12口新护士条例颁布实施后，我国大部分医院实行“APN”时间排班制。“APN”时间制，即每天平均分为3个班次:其中A班（8:0016:00）,P班（16:000:00）,N班（0:008:00,若将“休班”定义为R（rest）班，那么护士的排班主要指A班、P班、N班和R班。其中“APN”充分保证了高峰时段的护理安全。强约束条件（HardCoiistraintJIC）是在我国任何医院的护士排班环境中都必须满足的约束条件，否则整个排班表就不可行。强

7、约束条件主要考虑劳动法规、医院的护理资源和班次约束等：HC1:A班和P班均有1-2名中级资质以上的护士；HC2:任何一个班次（A班、P班和N班）的护士数不低于实际需求量；HC3:每位护士一天最多只能进行一个班次的工作；HC4:任何护士在相邻2天的班次不能连续（若第1天排N班，则第2天不能排A班）;HCS:在一个排班周期内，每位护士的最长工作班次不能超过规定的上限；HC6:在一个排班周期内，每位护士的最短工作班次不能少于规定的下限；HC7:在一个排班周期内，每位护士的最长连续N班不能超过规定的上限；HC8:在一个排班周期内，每位护士的最长连续班次不能超过规定的上限；弱约束条件（SoftConst

8、raint,SC）是指在医院实际护士排班中尽可能多的去满足的条件，各所医院在实际排班巾将弱约束条件进行调整和增加，本文中主要考虑护士的周末休息和排班的公平性：SC1:尽可能多的护士在周末至少休息一天；SC2：不对某个护士特殊照顾A班；如果护士的排班表满足了所有的强、弱约束条件，则为可行的护士排班表，如表31所示：表3-1可行护士排班表周一周二周三周四周五周六周口1AAPRNNR2RANNRPNNPNNRAAR32护士排班模型护士排班模型的目标就是在一个排班周期内（一周或一月），满足一系列劳动法规、案例模型医院护理资源需求和班次约束条件下，使得整个医院的护理成本最小化和护士工作的满意度最高。旨在

9、降低医院的护理运营成本，同时有效降低护士工作压力，让护士更好的处理好工作、生活和家庭的关系、从而提高医院的护理工作效率。参数假设：I=1,2,.n表示n名护士集合；T=1,2,。表示一个排班周期内的天数集合；K=1,234表示每天班次的类型（ARNE）;m表示在一个排班周期内，每位护士的最长工作时间；w表示在一个排班周期内，每位护士的最短工作时间；m表示在一个排班周期内，每位护士连续夜班的最长时间；叱表示在一个排班周期内，每位护士连续班次的最长时间；G#表示第i位护士在第j天选择第k个班次工作的工资等级，记为=12,3,4,5;尔表示在第j天第k班次对护士的需求量；Pxk表示第i位护士对第k个

10、班次的工作满意度，记为p11Kl（非常不满意）,2（不满意），3（一般）,4（满意），5（非常满意）;xljk=l表示第i位护士在第J天安排第k个班次，反之xljk=0;1,中级及以上职称0,其他Ai表示工资成本权重系数，其中凡人代0,1;入2表示班次满意度权重系数，其中人2印01；基于上述定义的参数，我们建立如下护士排班模型：minF(x)=fi(x),f2(x)其中nJ4fl(x)=WWWcMiiki=lj=lk=lnI4f2(x)=ww”ikxijki=lj=lk=lS.t.HC1：i)n1 2,1<qiXij22VieI,VjeTi=li=lHC2:nWXijkN"Vj

11、GT,kG1,2,3i=lHC3:4耿=1VielVjGTk=lHC4:Xij3+<1ViCI,VjCT(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)(3-7)HC5:案例模型J3(3-8)gXijkwmVieIHC6:HC7:HC8:SCI:SC2:J3WWxijkNwViGIfcl(3-9)r+iiiVXij3<niViGI,rG1,2,J-nx)(3-10)r+n23xijk<n2ViGI,re1,2,.,J-nJj=rk=l(311)+xi(j+i)421ViW1,2,.,10),VjGT(3-12)(3-13)x23(j)i=°VjET护士排

12、班模型要求在任何排班中强约束条件都必须满足，并尽可能多的满足弱约束条件。可根据实际环境中的重要性程度将弱约束做出如下的顺序:SCISC2,其中表示优先级，优先级的顺序由医院决定。由此可将目标函数(31)化为：2其中w入i=ii=l(3-14)2min户Q)=2入/Q)，i=ls.t.HC1:HC8,SCI,SC2模型(314)是一个典型的01整数规划模型，包含4*n*J个01决策变量，以及(17+2n)升(24iiE】2)n个约束方程。由于是在固定周期T内进行n位护士排班，并假设每口分4个班次，故模型的求解难度与护士数量呈线性关系。模型算法4护士排班算法4.1整数规划整数线性规划（Intege

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

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

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

16、行；（3）子问题的上界等于或小于己知的可行解的目标函数值。步骤5（最优性）:重复上述过程，直到分支定界树中没有需要考虑的节点（子问题），则当前最好的可行解就是原问题（IP）的最优解.4.2 模拟退火算法组合优化（CombinatorialOptimization）问题的目标就是从组合问题的可行解空间求出最优解，一般包含变量、约束和目标函数这三个基本要素。在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。求解组合优化问题就是在目的函数的解集合里找到最适合的解，这必然要求运用一定的算法去降低求解过程的时间复杂性和空间复杂性。Kirkpatri

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

18、止温度Tf,令迭代指标k=0,Tk=T0o第2步:随机产生一个领域解jN(i),(N(i)表示i的领域)，计算目标值增量Af=fG)-f(i)o第3步:若AfV0,令i4转第4步：否则产生随机量g=U(O,1),若exp(-勖>；,则令i=j°k第4步:若达到热平衡(内循环次数大于n(Tk)转第5步：否则转第2步。第5步:降低Tk，k=k+l,若Tk<Tf，则算法停止，否则转第2步。上述模拟退火算法流程如图4.1所示。图4.1SA算法流程图4.3 整数规划与模拟退火混合算法在护士排班领域研究中，一些算法的混合优化技术已经存在很多年了。国外将整数规划和领域搜索算法的混合优化

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

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

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

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

23、XX医院重症科室采取的是“弹性排班”制，每周的排班表由护士长根据科室的护士需求量和护士的家庭、生活状态等约束手工排班而成，详细的手工排班表如下表5-3所示。表5-3护士原始排班表序号周一周二周三周四周五周六周口1APRNNAP2APPRAPN3PANRAPA4APNRAAP5PRPRAAP6RRPAPNN7APPRPNN8APPRPAP9PRNNRPA案例计算与分析10PRNNRPP11PAARPNR12PAPNPPN13PRAPARN14PRANNRP15NNRAPAP16RNRRPNP17NNRAPAN18NNRPNRA19RPAPRPA20RPAPNRA21RAAPPRP22RAPNRA

24、P23NRPARPA24RPAARNP25RPRPNNN26RNNRRPP27NNRpAPN28RNNRAPP29RAAPRPP30RPPANRA由于每位护士在不同班次内的工资成本是不一样的，定义工资成本为5个等级，5代表最高级别的工资，1代表最低级别的工资，30位护士的工资级别如下表54所示：表5-4护士工资表阴1234567891011121314U16171819202122则中初中初初中初初初初初初初初初中初初初初初初232432222222223222222案例计算与分析23中344224初233125高455326高455327中344228初233129中344230初1331每

25、位护士对各个班次的工作满意度是不一样的，定义班次满意度为5个级别，1=非常不满意，2=不满意，3二一般，4=满意，5=非常满意，为了计算的统一性，将对R班定义为非常满意，详细的班次满意度表见下表55所示表5-5护士班次满意度序号APNR1532525325325154251555215615157251585215925151025151152151252151312551425151525151625151725151812551925152015152112552212552352152425152512552612552753252853252925153025155.2 分支界定法计算

26、结果在MATLAB上用分支界定算法对护士排班模型进行仿真实验，并令人1=0.乃，入案例计算与分析2=0.25,其计算结果如表56所示。表5-6护士排班模型计算结果手工排班表仿真排班表偏差目标值252.5155.75-38.17%工资成本575522-9.22%班次满意度71594331.19%运行时间/11.29s/其中，目标值偏差=仿式目标值一手工目标值*0%手工目标值0o工资成本和班次满意度的偏差类似计算。从表56可见，护士排班模型的目标值比实际手工排班的目标值低38.17%,其中护士工资成本降低9.22%,但是护士对班次的满意度提升了31.19%。这表明:基丁强、弱约束的护士排班模型明显

27、优丁手工排班模式,并且医院管理成本和护士对工作的满意度得到了有效的改善。5.3 模拟退火算法仿真结果在MATLAB上用模拟退火算法对护士排班模型(2214)进行仿真，采用近邻编码，取初始状态to=lOOOl,退温策略选用指数倒退函数，B|Jtk=Atk4,退温速率入=0.99,迭代终止策略为连续20代不变。如此的算法收敛情况如图5.1所示，所得结果如表57所示。图5.ISA算法收敛图表5-7护士排班模型计算结果手工排班表仿真排班表偏差目标值工资成本班次满意度运行时间252.5143-43.4%575513-10.8%71596735.24%/5.08s/案例计算与分析从表57可知，护士排班模型

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

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

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

31、:27-29姜小鹰.护理管理学国.上海:上海科学技术出版社，2001:139-143BelienJ,DemeulemeesterE.ABranchandPriceApproachforIntegratingNurseandSurgerySchedulingJ.EuropeanJournalofOperationalResearch,2008,189(3):652-668AickelfinU,LiJ.AnEstimationofDistributionAlgorithmforNurseSchedulingJ.AnnalsofOperationsResearch,2007,155(1):28930

32、9BardJEPurnomoHWCyclicPreferenceSchedulingofNursesUsingaLagrangianBasedHeuristicJ.JournalofScheduling,2007,10(1)：5-23HolmesE.Miller,WilliamP.Pierskalla,etal.NurseSchedulingUsingMathematicalProgrammingJ.OperationsResearch,1976,24(5)：857-870D.MWarner.Schedulingnursingpersonnelaccordingtonursingprefere

33、nce：AmathematicalprogrammingapproachJ.OperationsResearch,1976,24(5):842-856B.Jaumard,FSemet,andT.Vovor.AgeneralizedlinearprogrammingmodelfornurseschedulingJ.EuropeanJournalofOperationalResearch,1998,107(1):1一18Ozkarahan,J.E.Bailey.GoalprogrammingmodelsubsystemofaflexiblenurseschedulingsupportsystemJ.HETransactionsonIndustrialElectronics,2003,50(3):833838MaenhoutB,UanhouckeMComparisonandHybridizationofCrossoverOperatorsfortheNurseS