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

1、管理系统建模与优化期末作业护士排班问题专业：管理科学与工程时间：2015年1月目录 TOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 1案例背景3 HYPERLINK l bookmark10 o Current Document 2研究现状3 HYPERLINK l bookmark12 o Current Document 3案例模型4护士排班问题4护士排班模型4 HYPERLINK l bookmark22 o Current Document 4护士排班算法7整数规划7模拟退火算法7数规划与模拟退火混合算法8 HYPERLIN

2、K l bookmark24 o Current Document 5案例计算与分析10案例数据10分支界定法计算结果12模拟退火算法仿真结果13分支界定与模拟退火算法混合仿真结果14 HYPERLINK l bookmark33 o Current Document 6结论15 HYPERLINK l bookmark35 o Current Document 参考文献16研究背景及现状护士排班问题1案例背景护理工作是整个医疗卫生工作的重要组成部分，在医疗实践中担负着特殊的工作和 任务，是整个医院开展医疗服务的运营基础。目前各国护士短缺严重，已引起了国外护 理管理的高度重视1。我国护士长期处

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

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

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

6、患者服务，有 效改善医患关系，促进社会的和谐发展。案例模型3案例模型3.1护士排班问题护士排班问题是一种满足系列劳动法规和班次约束的护理资源最优分配问题。在实 际的护士排班中，约束条件主要包括匚作强度要求、夜班班次要求、护士对匚作环境的 满意度、工作时段的偏好和排班公平性等。护士排班问题的目标就是在一个排班周期内 （一周或一月），满足一系列劳动约束和医院资源需求的约束，使得整个医院的护理成本 最小化和护士工作的满意度最高。护士排班问题要服从以下的三个关犍假设：（1）护士排班模型的约束条件必须符合我国现行的劳动法规和大型医院护理工作 实际状况。（2）护士的自身的要求要尽量去满足，这对于护士排班问

7、题的研究是很重要的。（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）是在我国任何医院的护士排班环境中都必须满足的 约束条件，否

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

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

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

11、第k班次对护士的需求量；Pxk表示第i位护士对第k个班次的工作满意度，记为p11Kl（非常不满意）,2（不满 意），3（一般）,4（满意），5（非常满意）;xljk=l表示第i位护士在第J天安排第k个班次，反之xljk=0;1,中级及以上职称0,其他A i表示工资成本权重系数，其中凡人代0,1; 入2表示班次满意度权重系数，其中人2印01；基于上述定义的参数，我们建立如下护士排班模型：min F(x) = fi(x),f2(x)其中n J 4fl(x)= WWWcMiiki=l j=l k=ln I 4f2(x) = ww” ikxijki=l j=l k=lS.t. HC1： i)n2,1

12、qiXij2 2 Vi e I, Vj e Ti=li = lHC2:nW Xijk N VjGT,kG 1,2,3i=lHC3:4耿=1 VielVjGT k=lHC4:Xij3 + 1 Vi C I, Vj C T(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)(3-7)HC5:J 3(3-8)g Xijk w m Vi e IHC6:HC7:HC8:SCI:SC2:J 3WWxijkNw Vi G I fcl(3-9)r+iiiV Xij3 ni Vi G I, r G 1,2,J - nx)(3 - 10)r+n2 3xijk ；, 则令i=jk第4步:若达到热平衡(内循环

13、次数大于n (Tk)转第5步：否则转第2步。第5步:降低Tk，k=k+l,若TkTf，则算法停止，否则转第2步。上述模拟退火算法流程如图4.1所示。图4.1 SA算法流程图整数规划与模拟退火混合算法在护士排班领域研究中，一些算法的混合优化技术已经存在很多年了。国外将整数 规划和领域搜索算法的混合优化策略应用于护士排班领域，有效的改善了解的质量和算 法的效率。基于上述的研究，本文提出整数规划和模拟退火算法混合优化策略处理护士 排班问题的约束条件和护士的潜在要求，从算法的优化机制融合、算法结构互补、优化 操作的结合、优化行为的互补和削弱参数的苛刻条件等方面61阐述了混合优化机制的 优越性，其中整数

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

15、流程如图4.2所示。图4. 2BBASA算法流程图案例计算与分析5案例计算与分析案例数据本文的护士数据来源于XX医院护士工作状况调研问卷的调研结果。目前某三 甲医院重症科室共有30名护士，其中高、中、初级护士分别3, 5和22位。假设排班周 期为一周0=7),并将每天的工作时间平均分为a班(8:0016: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小时左右

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

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

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

19、示：表5-4护士工资表阴 1234567891011121314U16171819202122则中初中初初中初初初初初初初初初中初初初初初初232432222222223222222案例计算与分析23中344224初233125高455326高455327中344228初233129中344230初1331每位护士对各个班次的工作满意度是不一样的，定义班次满意度为5个级别，1=非 常不满意，2=不满意，3二一般，4=满意，5=非常满意，为了计算的统一性，将对R班 定义为非常满意，详细的班次满意度表见下表55所示表5-5护士班次满意度序号APNR1532525325325154251555215

20、61515725158521592515102515115215125215131255142515152515162515172515181255192515201515211255221255235215242515251255261255275325285325292515302515分支界定法计算结果在MATLAB上用分支界定算法对护士排班模型进行仿真实验，并令人1=0.乃，入案例计算与分析2=0.25,其计算结果如表56所示。表5-6护士排班模型计算结果手工排班表仿真排班表偏差目标值252.5155.75-38.17%工资成本575522-9.22%班次满意度71594331.19%

21、运行时间/11.29s/其中，目标值偏差=仿式目标值一手工目标值* 0%手工目标值0o工资成本和班次满意度的偏差类似计算。从表56可见，护士排班模型的目标值比 实际手工排班的目标值低38.17%,其中护士工资成本降低9.22%,但是护士对班次的满 意度提升了 31.19%。这表明:基丁强、弱约束的护士排班模型明显优丁手工排班模式, 并且医院管理成本和护士对工作的满意度得到了有效的改善。模拟退火算法仿真结果在MATLAB上用模拟退火算法对护士排班模型(2214)进行仿真，采用近邻编码， 取初始状态to=lOOOl,退温策略选用指数倒退函数，B|J tk=A tk4,退温速率入=0.99,迭 代终

22、止策略为连续20代不变。如此的算法收敛情况如图5.1所示，所得结果如表57所 示。图5. ISA算法收敛图表5-7护士排班模型计算结果手工排班表仿真排班表偏差目标值 工资成本 班次满意度 运行时间252.5143-43.4%575513-10.8%71596735.24%/5.08s/从表57可知，护士排班模型的目标值比实际手工排班的目标值降低了 43.43%,其 中工资成本降低10. 8%,但是护士对班次的满意度却提升了 3 5.24%。这表明:基于强、 弱约束的护士排班模型明显优于手工排班模式，在医院1：资成本控制和护士的满意度提 开方面达到了有效的平衡，而基于模拟退火算法的成功应用护士排

23、班模型，对求解大规 模的护士排班问题带来新的启发和思路。分支界定与模拟退火算法混合仿真结果参数选择与SA仿真相同。混合算法结果如表58所示，收敛情况如图5.2所示。图5.2SA算法收敛图表5-8护士排班模型计算结果手工排班表仿真排班表偏差目标值252.513347.32%工资成本575504-10.96%班次满意度71598037.6%运行时间/8.76s/基于分支定界和模拟退火算法的混合优化策略求得目标值比手工排班低47.32%,其 中工资成本下降10.96%,而护士工作班次满意度上升37.6%。这表明:基于分支定界和 模拟退火算法的混合优化策略明显强于原始的排班表，在护士排班模型的求解中能

24、取得 好的效果。结论6结论（1）基于分支定界和模拟退火算法的混合优化策略融合了分支定界和模拟退火算 法优化机制融合、算法结构互补、优化操作的结合、优化行为的互补和削弱参数的苛刻 条件等优点，综合评价最好，其护士排班模型的优化性能和算法的效率远远好于传统的 数学规划和单一的启发式算法。（2）基于强、弱约束的护士排班模型明显优于手工排班模式，并且医院管理成本和 护士对工作的满意度得到了有效的改善。其中增加的“APN排班”机制能有效的应付高 峰时段护理压力和错开上下班的交通高峰期;更多的护士在周末可以休息将有效改善护 士的家庭关系，而排班的公平性护士，提高护士的身心健康，使得整个医院的护理工作 更加

25、高效的开展和管理。参芍文献1345789101112131415参考文献刘玉宽，张莉，李梅.医疗卫生机构陷入困境的原因和出路灯.中国卫生经济, 1999, 18(6):15 16丰雪荣，华正丽.护士的压力源分析及应对措施J.中国医药指南，2011,9(33):153-154范淑玉等.我国护士排班状况研窕进展J.护士管理杂志，2008, 8(12) :27-29 姜小鹰.护理管理学国.上海:上海科学技术出版社，2001:139-143Be lien J, Demeulemeester E. A Branch and Price Approach for Integrating Nurse and

26、Surgery Scheduling J. European Journal of Operational Research, 2008, 189(3): 652-668Aick elfin U, Li J. An Estimation of Distribution Algorithm for Nurse Scheduling J. Annals of Operations Research, 2007, 155 (1): 289 309 Bard J E Purnomo H W Cyclic Preference Scheduling of Nurses Using a Lag rangi

27、anBased Heuristic J. Journal of Scheduling, 2007, 10(1)： 5-23 HolmesE. Miller, William P. Pierskalla, et al. Nurse Scheduling Using MathematicalProgramming J. Operations Research, 1976, 24 (5)：857 - 870 D. M Warner. Scheduling nursing personnel according to nursing preference： Amathematical programm

28、ing approach J. Operations Research, 1976, 24(5):842-856B. Jaumard, F Semet, and T. Vovor . A generalized linear programming model for nursescheduling J. European Journal of Operational Research, 1998, 107(1):1 一 18Ozkarahan, J. E. Bailey. Goal programming model subsystem of a flexible nursescheduli

29、ng support system J. HE Transactions on Industrial Electronics, 2003, 50(3) :833 838M aenhout B, Uanhoucke M Comparison and Hybridization of Crossover Operators for the Nurse Scheduling Problem J. Annals of Operations Research, 2008, 159 (1)：333 353Burk EK, Curtois T, Post q et al. A Hybrid Heuristic Ordering and Variab1eNeighborhood Search f or the Nurse Rostering Problem J. European Journal of Operat TonalResearch, 2008, 188(2)： 330-3