基于模拟退火的护士调度算法研究NP难问题毕业论文.doc

基于模拟退火的护士排班算法研究摘要随着经济的发展，国内外医疗问题越来越受注。护士是医疗机构中的重要成员。护士排班是医院日常工作的重要方面。科学合理的护士排班能降低医院的人力资源成本，提高护理质量。护士排班是基层护理者的一项经常性工作，是在现有的人力资源基础上，对护理工作任务、内容、程序、人力、和时间因素通盘考虑，做出系统、科学地安排，使护理人员明确职责，工作效率得到提高，保证医院护理质量，同时降低人力资源成本 赵美玉.护理管理学M.郑州：郑州大学出版社，2004：。由于护士排班问题受各种劳动法规约束，不同护士的能力有差异以及护士有班次偏好需求，护士排班问题是极为复杂的组合优化问题，属NP难问题。本文旨在利用模拟退火算法求解该问题。本文首先对护士排班问题建立整数规划模型，考虑护士级别和偏好，在减少医院成本的同时，尽量满足护士对于班次的偏好。然后探讨用模拟退火算法求解护士排班问题。详细设计了模拟退火算法，首先在不破坏一些约束的情况下（如晚班后不能接着上早班），随机产生初始解，然后用增加护士和减少班次的方法对初始解进行可行化，再在不破坏解的可行性的情况下，对排班表进行变换来产生新解，构成模拟退火的关键部分，再设计接受准则和算法参数，完成了算法的设计。最后，在C+ builder 6.0环境中进行编程实现，对湖南省某市级医院某科室的护士排班问题就行求解，取得了良好的效果。 关键字：护士排班；建模；模拟退火算法Study on Nurse Scheduling Algorithm Based on Simulated AnnealingAbstractAs the rapid development of economy, health organization is highly concerned at home and abroad. Nurses are important members of health organization. Nurse scheduling is an important part of daily operation in hospitals. Scientific and reasonable nurse scheduling can not only reduce the operating costs of hospitals but also improve the quality of nursing work. Nurse scheduling is a normal job of nurses at basic level, considering the nursing work, content, process, personnel, and time factors, which is making systematic and scientific plan to make nurses clear about their work, improve the proficiency and quality of their work and reduce personnel cost. Because nurse scheduling problem is constrained by many rules of labor law and there are differences of abilities and preferences between different nurses, nurse scheduling is a combination optimization problem, belonging to NP hard problem. The thesis has built the integer programming of nurse scheduling problem, considering the levels and preferences of nurses. The thesis tries to use simulated annealing method to solve the nurse scheduling problem. At first, initial solution is generated randomly. At the same time, the up work time of a nurse is protected not to be broken and other constrains are concerned, for example, when a nurse gets a night shift, he cant get the morning shifts the other day. Then adding nurse and subtracting shift methods are used to make the schedule feasible. In addition, much iteration is used to make the schedule better. Finally, programs are written in C+ builder environment and good result is reached. Key words: nurse scheduling, model, simulated annealing algorithm目录摘要IAbstractII1绪论11.1 选题背景和意义11.2国内外研究现状11.2.1国内研究现状21.2.2国外研究现状31.3 研究内容与组织结构32 护士排班问题建模52.1 护士排班问题52.2 护士排班问题整数规划模型63 基于模拟退火的护士排班算法73.1 模拟退火算法概述73.2 基于模拟退火的护士排班算法设计93.2.2 方案可行化113.2.3 新解的产生123.2.5 接受准则143.2.4 参数设计144 基于模拟退火的护士排班算法实现与案例分析144.1 案例背景144.2 算法实现154.2.1 类的设计154.2.2 模拟退火算法实现164.3 结果分析165 总结与展望185.1 总结195.2 展望19致谢19参考文献201绪论1.1 选题背景和意义 近年来，国内外医疗问题越来越受重视。护士是一种需要经过专业训练的人力资源、是医院日常运营的基础。护士排班问题也属于医疗问题的一个方面。目前世界各地（特别是在发达国家）的护士资源不足的问题越来越严重，受到了广泛重视。但是在我国管理机构对护士资源的重视度尚不够，致使很多地方出现护士严重不足的问题。护理人力资源与病人期望非常不平衡，临床护士编制严重不足，护士班次更换频繁，病人没有相对固定的护理人员，整体护理难以真正落实到位，如何通过管理合理使用人力资源，从而解决人力短缺问题，值得我们不断探讨与研究 院陆蕊,君鲍学,英王惠芬.护士排班的改进与实践J.护理管理杂志，2008，（02），23.。此外，传统的护士排班方法采用手工排班方法，这样显得混乱无序，而且效率低下。随着生活水平的提高，大众对于护理工作的要求也必然随之提高。因此提高护士利用效率非常有必要。运用计算机算法生成排班表，既能提高准确度又提高了效率。从护士数量、结构、配置、分工（排班）等，实施人性化排班。提高护士工作积极性和主动性，使排班具有规律性、提高了管理效率。 护士排班是基层护理者的一项经常性工作，是在现有的人力资源基础上，对护理工作任务、内容、程序、人力、和时间因素通盘考虑，做出系统、科学地安排，使护理人员明确职责，工作效率得到提高，保证医院护理质量，同时降低人力资源成本1。护士排班问题已经成为医院管理的核心内容之一。但是由于排班中存在一系列劳动法约束，外加需要考虑不同护士的能力级别差异，因此，护士排班问题是极为复杂的组合优化问题，属NP难问题，在国外深受研究关注。在解决组合优化问题时，元启发式算法能起到很好的作用。本论文用模拟退火方法研究护士排班算法。 护士排班研究属于护理研究的一部分。现代医学不断发展，对护理工作也提出了更高的要求。研究护士排班问题对于提高护理水平有重要作用，对于促进护理学与先进的医学同时前进具有重大意义。 1.2国内外研究现状 对于护士排班问题，国外的研究较早，很多人用了很多科学方法来优化，而国内的研究较少，很多都停留在手工排班方法，用算法优化的比较少。1.2.1国内研究现状 由于国内的研究大部分都停留在定性方面，从排班类型，排班原则，排班方式三个方面进行总结。另外，也有少数算法的研究。李秋洁 李秋洁护理管理M北京：人民卫生出版社，2003：6061提出排班类型依照排班权利的归属分为集权式排班(由护理部负责)、分权式排班(由护士长负责)及自我排班(由护士自行排班)3种。对于排班原则，吕芳 吕芳新型的以病人为中心的排班模式对护理的影响J现代护理2001，7(6)：51一52提出以病人的需要为基本原则：以病人的护理需要为中心，适应护理工作的连续性，24 h不间断，合理有效地安排人力，护理、教学、科研须统筹兼顾; 秦玉霞等 秦玉霞，李晓星，牛娟互补增值原理在护士排班中的运用J临床护理杂志，2002，l(1)：9一lO提出互补增值原则：掌握护理工作规律，分清主次缓急，合理搭配各层次人员，做到年龄、学历、资历、气质及技能互补，使工作互不重叠、互不干扰，既能保证重点，又能照顾一般; 杨玉霞 杨玉霞门诊护士排班方式的探讨J实用护理杂志，2003，19(2)：65 提出均衡平等原则：保持各班工作量的均衡，按工作量安排人力，一视同仁，各岗位轮转机会均等，使人人充分发挥效能。张萍 张萍ICU护理人员排班与人力资源利用J解放军护理杂志，2004，21(11)：78提出稳定机动原则：护理排班方式应相对稳定，护士长提前安排好下一周班次后向护士公示并上报护理部，使护士对自己的班次有预见性；常备机动人员，以便随时调配归。苟艳梅等 苟艳梅，刘小敏，任秋云，等护士排班需求本在手术室排班中的作用J中华护理杂志，2002，37(1)：5556 提出人性化原则:护士并非单一角色，除工作中的职业角色外，还有社会角色，应以入为本，尽量满足护士的合理要求。对于排班方式，戴琴、周力等 戴琴，冯植重症监护病房护士工作压力源与心理健康水平的相关性研究J中华护理杂志，2002，37(7)：488489 -周力，赵琳，徐梅，等手术室实施弹性排班制度效果评价J护理管理杂志，2002，2(2)：5759提出按功能制护理模式排班实行全院统一排班的方式，按功能制护理方式分配岗位，按岗位配备护士，由白班、中班、前夜班、后夜班组成，每名护士1个班次值l d，循环进行。白班人员有45名，中午、夜班只有1名护士值班，其缺点是白班人员多、夜班人员少，遇到病重、手术病人多或抢救时难以应付，无暇顾及其他病人。该排班方式是我国医院护士排班最常用的，也是近年来要求改革的一种方式，适用于急诊、危重病人较少的五官科、肿瘤化疗科及康复科等。何丽等 何丽，绳宇，宋烽弹性排班与手术宦护士资源分配的研究J。解放军护理杂志，2003，20(2)：3738 提出按整体护理模式排班将病区工作分为临床组与办公室组。办公室组值白班，有利于高年资护士及特殊时期护士(妊娠及哺乳期)的合理利用，体现了“以人为本”的管理理念；临床组实施以责任护士负责制的小组或整体护理，相对固定，分组负责病区全都病人的健康教育、基础护理及中、晚班工作。每组由各层次护士组成，责任护士值白班，3个月轮转1次，有利于病人的全程护理，并通过与医生共同查房，充实了专科知识及避免医护间的不一致。该排班方式适用于整体护理模式病房及护理人员充足的科室，值得注意的是排班时应遵循“互补增值”原则。做到年龄、学历、资历、气质、技能及能力互补，形成团队合力，扬长避短，全员参与管理。班次分类、排班原则和排班方法都是一些定性方面的研究，随着研究的不断深入，也产生了很多定量化的研究，用到了不少科学方法。沈吟东等沈吟东,陈名晖,邓婕.利用矩阵向量化变换求解护士排班问题C.中国控制与决策会议论文集,2008:1019-1022.利用矩阵向量化变换来求解护士排班问题。刘晓荣等刘晓荣,顾仁萍,袁长蓉,陈国良,孙庆文,毛燕君. 护士排班决策支持系J. 解放军护理杂志, 2006(1): 67-69.设计了一种能同时满足医院和护士需求的更具弹性的决策支持系统，它采用了选择性模型，而这些模型又融合了弹性工作方式，因为它结合了每天24h每周7d的排班问题，并给出了弹性护上排班图和决策支持系统的结构。1.2.2国外研究现状 国外的护士排班研究可以分为三个阶段，早期的数学方法，随后的人工智能法，近期的元启发式算法。很多早期论文 H.E.Miller,W. Pierskalla, G. Rath:Nurse scheduling using mathematical programming, OperationsResearch, Vol. 24, 1976, 857870., M. Warner, J. Prawda: A mathematical programming model for scheduling nursing personnel in a hospital, Management Science, Vol. 19, 1972, 411422., V.M. Trivedi, M. Warner: A branch and bound algorithm for optimum allocation of float nurses,Management Science, Vol. 22, No. 9, 1976, 972981., M. Warner: Scheduling nursing personnel according to nursing preference: A mathematical programming approach, Operations Research, Vol. 24, 1976, 842856.都为他们的线性模型提到数学优化方法。数据的简化是不可避免的。现实世界的问题很复杂以致难以用线性规划的方法优化，当护士的人数、排班时间和约束个数增加时，该方法就陷入了“维数灾”。后来很多学者采用启发式算法（如 R. Blau: Multishift personnel scheduling with a microcomputer, Personnel Administrator, Vol. 20,No. 7, 1985, 4358., M.Kostreva,K.Jennings:Nurseschedulingonamicrocomputer,Computers and Operations Research,18, 1991, 731739.,L.D. Smith, D. Bird, A. Wiggins: A computerised system to schedule nurses that recognises staff preferences, Hospital & Health Service Administration, 1979, 1935.,L.D. Smith, A. Wiggins: A computer-based nurse scheduling system, Computers and Operations Research, Vol. 4, No. 3, 1977, 195212., S.J.Darmoni,A.Fajner,N.Mahe,A.Leforestier,O.Stelian,M.Vondracek,M.Baldenweck:Horoplan:）。定义多个目标也是常见的，如 I. Berrada, J. Ferland, P. Michelon: A multi-objective approach to nurse scheduling with both hard and soft constraints, Socio-Economic Planning Science, 30, 1996, 183193., J.-G. Chen, T. Yeung: Hybrid expert system approach to nurse scheduling, Computers in Nursing,1993, 183192.,J. Arthur, A. Ravindran: A multiple objective nurse scheduling model, AIIE Transactions, Vol. 13,No. 1, 1981, 5560., A. Musa, U. Saxena: Scheduling nurses using goal-programming techniques, IEEE, 1984, 216221.,I. Ozkarahan: A disaggregation model of a flexible nurse scheduling support system, Socio-Economical Planning Science, Vol. 25, No. 1, 1991, 926.,A. Jaszkiewicz: A metaheuristic approach to multiple objective nurse scheduling, Foundations of Computing and Decision Sciences, Vol. 22, No. 3, 1997, 169184.。 20世纪80年代以来，人工智能被应用于护士调度问题（陈述方法S.J.Darmoni,A.Fajner,N.Mahe,A.Leforestier,O.Stelian,M.Vondracek,M.Baldenweck:Horoplan:computer-assisted nurse scheduling using constraint based programming, Journal of the Society forHealth Systems, Vol. 5, 1995, 4154.30 A. Meisels, E. Gudes, G. Solotorevski: Employee timetabling,constraintnetworks and knowledgebasedrules: A mixed approach, In E.K. Burke, P. Ross (Editors), Practice and Theory of AutomatedTimetabling; First International Conference Edinburgh, Springer, 1995, 93105.31 H. Meyer auf m Hofe: ConPlan/SIEDAplan: Personnel assignment as aproblem of hierarchical constraint satisfaction, Proceedings of theThirdInternational Conference on the Practical Applicationof Constraint Technology, London, 1997, 257271.32 M. Okada: An approach to the generalised nurse scheduling problem-generation of a declarative program to represent institution-specific knowledge, Computers and Biomedical Research, Vol. 25,1992, 417434.33 P. Chan, G. Weil: Cyclical staff scheduling using constraint logic programming, In E.K. Burke,W. Erben (Editors), Practice and Theory of Automated Timetabling; Third International Conference,Konstanz, Springer, 2000, 159175.34 G.R. Beddoe, S. Petrovic, G. Vanden Berghe: Case-based reasoning in employee rostering: learning repair strategies from domain experts, University of Nottingham. (Unpublished).35 S. Petrovic, G. Beddoe, G. Vanden Berghe: Storing and adapting repair experiences in personnel rostering, In E.K. Burke, P. De Causmaecker (Editors), Selected Revised Papers of the 4th International Conference on Practice and Theory of Automated Timetabling, LNCS 2740, 148168.36 M. Chiarandini, A. Schaerf, F. Tiozzo: Solving employee timetabling problems with flexible workload using tabu search, In E.K. Burke, W. Erben (Editors), Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, ISBN 3-00-003866-3, 2000, 298302.37 M.J. Brusco, L.W. Jacobs: Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations, European Journal of Operational Research, Vol. 86, 1995, 249261.38 M. Isken, W. Hancock: A heuristic approach to nurse scheduling in hospital units with nonstationary,urgent demand, and a fixed staff size, Journal of the Society for Health Systems, Vol. 2,No. 2, 1990, 2441.39 K. Dowsland: Nurse scheduling with tabu search and strategic oscillation.European Journal of Operations Research, Vol. 106, 1998, 393407.40 I. Berrada, J. Ferland, P. Michelon: A multi-objective approach to nurse scheduling with both hard and soft constraints, Socio-Economic Planning Science, 30, 1996, 183193.41 U. Aickelin, K. Dowsland: Exploiting problem structure in a genetic algorithm approach to a nurserostering problem, Journal of Scheduling, Vol. 3, No. 3, 2000, 139153.42 E.K. Burke, P. Cowling, P. De Causmaecker, G. Vanden Berghe: A memetic approach to the nurse rostering problem, Applied Intelligence Special Issue on Simulated Evolution and Learning, Vol. 15,No. 3, Springer, 2001, 199214.43 H. Kawanaka, K. Yamamoto, T. Yoshikawa, T. Shinogi, S. Tsuruoka: Genetic algorithm with the constraints for nurse scheduling problem, Proceedings of Congress on Evolutionary Computation,Seoul, IEEE Press, 2001, 11231130.44 F. Easton, N.Mansour: A distributed genetic algorithm for employee staffing and scheduling problems,Conference on Genetic Algorithms, San Mateo, 1993, 360367.45 J. Tanomaru: Staff scheduling by a genetic algorithm with heuristic operators, Proceedings of the IEEE Conference on Evolutionary Computation, 1995, 456461.46苏光辉.基于需求的护士优化排班问题研究D.武汉：华中科技大学控制科学与工程系，2009附录附录一、solution类的成员函数#include #include #includeSolution.husing namespace std;void Solution:initialize() int i,j,type,k,workdays; int temp_demand321; for(i=0;i10;i+) /给护士的级别赋值，10个低级护士，11个中级护士，7个高级护士 ,并给护士上班费用赋值 gradei=1; for(j=0;j21;j+) /i级别的护士的费用是i work_costij=1; for(i=10;i21;i+) gradei=2; for(j=0;j21;j+) work_costij=2; for(i=21;i28;i+) gradei=3; for(j=0;j21;j+) work_costij=3; for(i=0;i28;i+) /给work矩阵赋值。 假设为每个护士请一天的假， for(j=0;j7;j+) /前面四个护士星期一请假，第五到第八个护士星期二请假，依次推理 workij=1; workij+7=1; workij+14=1; type=i/4; workitype=0; workitype+7=0; workitype+14=0; for(i=0;i28;i+) /给pref矩阵赋值 for(j=0;j21;j+) prefij=1+(i%5+j%5)/2; work_gradeij=0; tabij=0; demand00=2; /给demand矩阵赋值 for(j=1;j6;j+) demand0j=1; demand06=2; demand07=4; for(j=8;j13;j+) demand0j=3; demand013=4; for(j=14;j21;j+) demand0j=2; demand10=3; for(j=1;j6;j+) demand1j=2; demand16=3; demand17=5; for(j=8;j13;j+) demand1j=4; demand113=5; for(j=14;j21;j+) demand1j=1; demand20=2; for(j=1;j6;j+) demand2j=1; demand26=2; for(j=7;j14;j+) demand2j=2; for(j=14;j21;j+) demand2j=1; for( i=0;i3;i+) for( j=0;j21;j+) temp_demandij=demandij; for( i=0;i28;i+) /对于七天循环，每天为护士分配一个班型，早中晚休， workdays=0; for( j=0;j=6) /如果请假或者是该护士一周已经达到了六个工作班次，那么该天的三个班次都赋值为0 tabij=0; tabij+7=0; tabij+14=0; else if(temp_demandkj0&(j=0|tabij+13=0) /没有请假，也没有达到六个班次，并且该班次对于该级别的护士有需求，且之前一个班次不是夜班 tabij=1; work_gradeij=gradei; /该班次赋值为1，工作班次加1，该班次对于该