手术室手术调度使用Metaheuristic方法与模糊手术持续时间

文摘

手术室(或)手术调度是一个具有挑战性的组合优化问题,确定每一个手术要执行的操作开始时间在不同的外科组,以及资源分配给每个手术安排一段时间。卫生保健系统的主要挑战之一就是以最低的成本提供最高质量的保健。在现实生活中,有重大不确定性的几个活动参与的外科治疗,包括手术的持续时间。本文解决了手术室手术调度问题和确定手术时间、手术持续时间的不确定性是由模糊数的方法。问题可以视为模糊柔性作业车间调度问题(FFJSP)由于相似性手术室手术调度不确定手术时间和multi-resource约束柔性作业车间调度问题和不确定的处理时间。本研究将先进的处理和分配调度问题,同时提供了一个蚁群优化(ACO) metaheuristic算法,利用两级蚂蚁图集成测序工作和分配资源在同一时间。评估该方法的性能,提出了一种计算研究五个测试手术病例,同时考虑确定性和模糊手术持续时间以提高研究的重要性。这个实验的结果证明了该metaheuristic算法的有效性。

1。介绍

手术室手术调度处理决定的手术操作开始时间和分配所需资源安排手术,考虑几个约束条件,以确保一个完整的手术流程。作为医院重要的组件,或据估计占40%以上的医院的总收入和类似的总费用的大部分(1]。

或管理由两个阶段组成:第一,计划为每个病人提供手术日期,考虑到手术室的可用性和外科医生。第二,日常调度决定了每天在每个手术室的操作序列,考虑材料和人力资源的可用性(2]。所以,这相当重要的改善或管理能够提供及时的治疗诊所的病人和一个有效的使用资源。此外,在现实生活中,有一个高度不确定性的重要性在各种活动参与手术护理和关注,包括更复杂的手术步骤的时间分配的决定。最近或规划和调度文学由[分类3]。此外,审查的取舍或规划提出了(4]。

一般来说,手术进展涉及不同的活动之前,期间和之后实际的外科手术。执行手术所需的资源也由人员如外科医生、护士、麻醉师和设施如术前控股单位(范围内),postanaesthesia护理单元(pacu)和重症监护病房。此外,替代等因素优先级服务,不同的外科专业,人员变化也必须考虑在内。

可以找到一些文件或手术安排在5- - - - - -9]。一个蚁群优化方法,介绍了由[10解决一个手术室手术调度问题。全面的分类根据手术持续时间(确定性或随机),病人到达(选择性和nonelective),和操作提出了策略的研究(6]。当活动持续时间仍高度不确定的时候,各种各样的方法被认为是处理许多有用的情况。评论可以在不确定情况下的调度的基本方法(11]。另外,随机规划过程为项目调度,处理时间不确定在哪里被随机因素可以发现在12]。最近,一个过程表明了(13)解决资源受限项目调度问题与不确定的活动时间,所以不确定时间是由独立随机变量与一个已知的概率分布函数。

混合两相优化算法是由14为手术调度),而滚动地平线的方法为病人选择和提出的任务是(15]。此外,提出一种系统化的方法是(16]帮助手术计划调度的选择性手术。一个两阶段的鲁棒优化选择性外科手术和下游容量规划是应用的17]。

模糊区间模糊数,或者更普遍的是,用于造型ill-known处理时间作为替代和补充的方法。模糊的方法已经存在了超过二十年,已经收到了几位研究者的注意18]。特别是,几个metaheuristics模糊作业车间调度问题,提出了自1990年代以来,如模拟退火法(19)、遗传算法(GA) (20.),粒子群优化算法(21),混合算法相结合的GA与当地一个非常有效的搜索方法(22),基于群体的社区搜索算法(23),一种混合算法,结合粒子群优化和禁忌搜索(24),和一个人工蜂群算法(25]。

灵活性的现实问题的另一个特点是考虑柔性作业车间调度问题,作业车间调度问题的一种变体,多台机器可以执行相同的操作。此外,模糊加工时间和灵活性的机器可以同时被考虑。这种情况被称为模糊柔性作业车间调度问题(FFJSP)。这将是本文问题考虑最大完工时间最小化的目标。

同时,灵活的作业车间调度问题被研究在1990年代首先解决。的方法(26- - - - - -28)获得最好的结果到目前为止对于许多柔性作业车间调度问题的实例。的组合的灵活性和不确定性FFJSP被一些研究如下:遗传算法给出了(29日)的混合人工蜂群算法(30.,使用的分布估计算法31日)的共同进化算法(32),或群附近搜索算法从[33]。

摘要手术室手术手术时间不确定调度问题解决,在手术持续时间的不确定性通过模糊数表示。问题可以视为FFJSP由于相似性手术室手术调度不确定手术时间和multi-resource约束柔性作业车间调度问题与不确定的处理时间。典型的手术病例调度问题的混合决策水平通常包括两个子问题:先进的调度(也称为或计划)和分配调度。很明显,这两个子问题通常制定单独的组合优化模型。与大多数在这个领域发表论文,本研究同时处理两种先进和分配调度问题和提供了一个蚁群优化(ACO)方法与两级蚂蚁图有效地解决这样的计算具有挑战性的问题。

本文的其余部分组织如下:部分2致力于手术调度环境。节3该算法的细节。部分4提供了计算实验来验证和评估的方法。最后,本文以部分5结论和未来研究的建议。

2。手术调度问题

我们可以在医院手术为选修或紧急手术。在本文中,选择性外科手术被认为是。这里,病人被运输机从住院病房或眼科手术单位。完整的选择性外科手术过程一般包括三个步骤:术前的(设置),在peri-surgery(手术),和对象(复苏)。在第一步,如果它是必要的,病人的基本信息和适当的注射将得到确认。如果给定的手术室不是准备好了,病人等范围内的安装步骤。在真正的手术步骤中,不同类型的操作是捐赠给不同手术时间和医疗小组。当所有所需的资源准备,手术就可以开始了。在第三步中,病人转移到PACU的复苏以及进一步治疗,例如,重症监护病房。毕竟,医务人员必须为另一个洁净手术室手术。

我们必须改变手术进展的时候如果任何资源在三步手术是没有及时提供,这影响或效率。大多数时候,一个完整的手术需要人员和设施。从本质上讲,主要设施资源多功能,可以支持不同种类的情况下,随着人力资源部门非齐次关于他们的手术,专业知识,经验,和一般的可用性。这篇文章只包含外科医生的不均匀性。然而,其他人员资源,比如护士和麻醉师是开放的任何手术,认为是多功能的。

据推测是一组手术有内执行一个操作集合各种资源。每一个手术是伴随着手术需求和资源需求。手术的需求是确定的具体手术专业和不确定手术时间,而资源需求意味着任何手术的完整步骤所需的所有资源。下一步就可以开始对所有可用的资源,对每一步骤的性能。调度的目标是最小化考。使用数学模型,这是香等人应用的优化模型求解手术室手术调度问题(更多细节见10])。

2.1。不确定的时间

在真实的应用程序中,通常情况下,外科手术的确切时间事先是未知的。这自然导致造型时间使用模糊区间或模糊数。模糊的时间间隔是一个模糊集和隶属函数实数吗 这样,其 - - - - - -削减 , ,时间间隔。如果它的一个模糊区间模糊数 - - - - - -削减表示 ,关闭,其支持吗 紧凑和有一个独特的模态价值 , 。

模糊区间的最简单的模型是一个三角形模糊数(TFN的),使用一个时间间隔可能的值和模态值在里面。对于一个TFN的 ,表示 ,成员函数接受下面的三角形: 模糊柔性工作车间,必须解决两个问题:最大完工时间最小的确切含义等考也是一个TFN的扩展添加的两个操作的方法和最大TFN的。

TFN的期望值是由 这导致总排序在模糊区间的设置,对于任意两个模糊区间和 , 当且仅当 。显然,对于任何两个tfn的和 ,如果 然后 。

关于之和,对任何一双tfn的和 , 同时,对于任何两个tfn的和 ,如果表示他们的最大和 其近似价值,它认为 在哪里是 - - - - - -切的 。特别是,和有相同的支持和模态值。这个近似被用于(34,35]。

3所示。蚁群算法对手术调度问题

本文开发的蚁群优化算法是解决不确定手术的手术调度问题持续时间。ACO最初是为了解决知名旅行推销员问题(TSP) [36]。原算法在TSP,有一只蚂蚁图中,每个节点对应于一个城市,和弧对应于城市之间的距离。蚂蚁遍历所有节点获得最低之旅。裁缝ACO手术调度问题,城市可以被映射到手术,一个节点旅游然后把手术的序列。然而,完整的手术调度不仅决定了测序的手术时间,也是资源配置的手术步骤。这里,两级蚂蚁图用于手术调度问题作为香等。10应用在他们的研究。两级分层ant图如图1。outer-graph中的节点代表了手术,和定向弧,指示优先序列,用于连接两个节点。inner-graph节点代表的总资源或管理系统涵盖完整的3步手术过程。

3.1。ACO算法描述

算法中,蚂蚁推翻化学信息素在移动环境。他们也能够检测并遵循费洛蒙。蚂蚁构建解决方案使用概率转换规则。本文介绍了两个转换规则的内在和外在ant图表。外手术图的概率一只蚂蚁会选择节点从节点定义如下: 在哪里是一个可行的节点集,和参数控制轨迹的相对重要性和可见性。每个蚂蚁构建解决方案使用的结合提供的信息外信息素踪迹节点之间和 ,通过启发式函数定义的 ,在哪里从节点代表了持续时间到节点 。

内部资源图的概率这只蚂蚁会选择资源为资源类型的手术定义如下: 在哪里是选择下一个可用的资源资源节点,内手术相关信息素, ,手术记录来标示信息链接资源在不同的步骤;和内部资源本身信息素, ,定义记录相关信息资源利用率而一个ant构建内部资源分配的解决方案。启发式函数被定义为 ,在哪里手术的时间吗在资源的资源类型 。

平衡资源利用率在任何手术步骤,一旦资源被选中时,由另一个手术应该被选中的机会减少。因此,本地更新在访问每个节点由以下平等。 在哪里是递减的信息素值。

让蚂蚁分享良好的信息解决方案,追踪信息素的更新必须建立。外层次图,当所有蚂蚁完成遍历节点,蚂蚁与最好的时间表迭代更新路径如下: 在哪里表示信息素的蒸发率,解决方案的时间,最大完工时间是最好的所有解决方案由一组蚂蚁。

我们内心的层次图,

4所示。计算实验

4.1。说明测试用例

提出的算法使用五个测试评估手术病例由湘et al。10),在手术时间和他们不同的需要或资源。他们分为五种类型,小,中,大,超大,特别。关于手术持续时间,不确定性是添加到时间基于从[34]。让是真正的手术时间,所以我们建立TFN的 在哪里 和和是随机的正整数的值验证 和 。如果不存在整数值区间 ,我们设置 ,如果没有整数值 , 需要一个随机值 。

这五个手术病例的信息表1,2,3。关于手术病例的更多细节,请参阅[10]。

4.2。设置参数值

蚂蚁系统中使用的设置参数值调度算法往往是非常重要的得到不错的结果。所有参数由不同的调整和最终试验显示在我们的论文中使用的参数如下:(我) :这种算法很适合一个值在1。(2) :值2似乎提供了最好的之间的权衡后,启发式和允许蚂蚁探索研究空间。(3) :信息素的蒸发参数测试的值范围0.1 - 0.99找到好的解决方案,最后一个值在0.2手术病例1和2和0.1在其他情况下被接受。(iv) :递减信息素值设置的值约为0.1。(v)蚂蚁的数量:约30蚂蚁在手术情况下1和2;50个蚂蚁在手术病例3,4,5。

4.3。实验结果讨论

ACO算法,用Matlab实现和运行使用笔记本与英特尔Core2双核运行Windows 7, 4 GB内存。此外,CPU时间变化根据测试用例的复杂性以及使用的蚂蚁数量。

提出的算法测试五个测试手术的情况下,考虑确定性和模糊手术持续时间。表4和5显示结果与模糊手术持续时间五个测试用例。在表4,列头考,所有手术的完成时间计划,包含考(TFN)连同其期望值。在下一篇专栏文章,标题加班记录所需的总额外的时间除了常规工作时间(8小时)。在这篇文章中,如果无法完成一个手术在10 h,它将被安排在第二天。这意味着授权加班也仅限于2 h。,工作时间的变异系数(VCWT)定义为均值的标准差的比值计算表5的预期值,不同的资源。

很明显从表4配电网调度实现考的一个工作日内,除了测试用例5。

资源的VCWT测试用例1和2所示图2。显然,VCWT减少测试用例2。此外,测试用例2是资源短缺情况下测试用例1。因此,ACO执行更好,尤其是面对资源短缺问题或管理的一个重要问题,因为目前更多的医院正面临护士短缺的问题。

关于确定性手术持续时间,提出的算法比较与香等报告的结果。10]。他们提出了一个蚁群优化方法来解决一个手术室手术调度问题。表6和7显示5个测试用例的结果。在表6给出了极小化和加班,而资源的工作时间的变异系数是计算表7。

很明显从表6提出的算法发现时间表少考比的方法10在例2和3。此外,在例5中,结果表明,所有的手术都必须完成,直到第二个工作日。从表可以看出7,ACO具有竞争力的价值资源的VCWT发现,这表明该算法可以产生一个时间表相对平衡的资源利用率。

5。结论

摘要手术手术时间不确定调度问题考虑不确定性在手术时间通过模糊数表示。此外,问题是复杂的,需要考虑整个三个步骤(设置、手术和恢复)与手术有关,开放的调度策略,以及多个资源约束。问题可以被描述为一个multi-resource约束模糊柔性作业车间调度问题。算法的方法,利用两级蚂蚁图开发有效地解决这个问题。两级分层ant图包含外手术图和内部资源图。的相对机制提出的算法,如启发式可见性、信息素更新规则,和状态转换规则。所有手术的目标是最小化最大完工时间的旨在实现次优的解决方案。

5测试用例在文献中被认为是与不同的手术问题大小和可用资源评估ACO算法。此外,不确定性增加了测试用例的时间建立模糊手术持续时间。算法的性能的计算结果五个测试手术的情况下,考虑确定性和模糊手术持续时间,也被提出了。关于确定性手术持续时间,该方法与一个蚁群优化方法的报道结果。在这个比较中,三个性能度量进行评估:考,加班,工作时间的变异系数。实验结果表明,该算法具有竞争力的解决方案的质量。对于未来的工作,它可能是有趣添加多样化在本地更新规则和使用本地搜索算法。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

补充材料

引用

1. 丹顿,j . Viapiano, a . Vogl”优化手术下排序和调度决策的不确定性,”卫生保健管理科学,10卷,不。1、24里面,2007页。视图:出版商的网站|谷歌学术搜索
2. j . m . Magerlein和j·b·马丁,“手术需求调度:审查。”卫生服务研究,13卷,不。4、418 - 433年,1978页。视图:谷歌学术搜索
3. m .制造c . Van Riet e . Demeulemeester b .赶到这里,克里斯丁n。梵斯丁凯斯特和f·e·说Rademakers”调度手术室:成就,挑战和缺陷,”杂志的调度,19卷,不。5,493 - 525年,2016页。视图:出版商的网站|谷歌学术搜索|MathSciNet
4. c . Van Riet和大肠Demeulemeester“权衡在手术室选修课和紧急情况的计划:一个评论,”运筹学为卫生保健卷。7日,52 - 69年,2015页。视图:出版商的网站|谷歌学术搜索
5. 布莱克和m .卡特,“手术进程调度:结构化的评论,”社会卫生系统杂志》上,5卷,不。3,相当于17 - 30,1997页。视图:谷歌学术搜索
6. b .赶到这里,大肠Demeulemeester和j . Belien”手术室规划和调度:一个文献综述,”欧洲运筹学杂志》上,卷201,不。3、921 - 932年,2010页。视图:出版商的网站|谷歌学术搜索
7. 美国埃尔多安a和b t·丹顿“手术规划和调度,”威利运筹学和管理科学的百科全书j·j·科克伦,l·a·考克斯·Keskinocak j . p . Kharoufeh Eds和j·c·史密斯。约翰•威利& Sons 2010。视图:谷歌学术搜索
8. f . Guerriero r·圭多,“运筹学在手术室的管理:一项调查,“卫生保健管理科学,14卷,不。1,第114 - 89页,2011。视图:出版商的网站|谷歌学术搜索
9. j . h, w·e·斯潘格勒,d . p .弹奏和l . g . Vargas”手术调度问题:当前研究和未来的机会,“生产工程的研究和开发,20卷,不。3、392 - 405年,2011页。视图:出版商的网站|谷歌学术搜索
10. w, j .阴,g . Lim,”一个蚁群优化方法求解手术室手术调度问题,“计算机与工业工程卷,85年,第345 - 335页,2015年。视图:出版商的网站|谷歌学术搜索
11. w . Herroelen和r .低浓缩铀项目调度下的不确定性:调查和研究潜力,”欧洲运筹学杂志》上,卷165,不。2、289 - 306年,2005页。视图:出版商的网站|谷歌学术搜索
12. 大肠Klerides和大肠Hadjiconstantinou”decomposition-based随机规划方法为项目调度问题在时间/成本平衡设置和不确定的时间,“电脑与行动研究,37卷,不。12日,第2140 - 2131页,2010年。视图:出版商的网站|谷歌学术搜索
13. m·e·布鲁尼p . Beraldi f . Guerriero和e·平托,“资源约束项目调度的启发式方法与不确定的活动时间,“电脑与行动研究,38卷,不。9日,第1318 - 1305页,2011年。视图:出版商的网站|谷歌学术搜索
14. r·p·兰达Aringhieri, p .索里亚诺e . Tanfani和A .包括“手术调度的混合优化算法,运筹学为卫生保健,8卷,第114 - 103页,2016年。视图:出版商的网站|谷歌学术搜索
15. b·阿迪斯g . Carello a格罗索,e . Tanfani”手术室调度和延期:滚动地平线的方法,”灵活的服务和生产日报28卷,第232 - 206页,2016年。视图:出版商的网站|谷歌学术搜索
16. 即品牌和m . Captivo Dierent涉众的观点对于手术情况分配问题:确定性和健壮的方法,”欧洲运筹学杂志》上卷,261年,第278 - 260页,2017年。视图:出版商的网站|谷歌学术搜索|MathSciNet
17. Neyshabouri和b·p·伯格”两级鲁棒优化方法选择性外科手术和下游容量规划,“欧洲运筹学杂志》上,卷260,不。1、意向,2017页。视图:出版商的网站|谷歌学术搜索|MathSciNet
18. d·杜布瓦h . Fargier, p . Fortemps”模糊调度:造型灵活的约束和应对不完整的知识,”欧洲运筹学杂志》上,卷147,不。2、231 - 252年,2003页。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. p . Fortemps”作业车间调度与不精确的时间:模糊的方法,”IEEE模糊系统,5卷,不。4、557 - 569年,1997页。视图:出版商的网站|谷歌学术搜索
20. d . Lei“解决使用随机密钥模糊作业车间调度问题的遗传算法,”国际先进制造技术杂志》上49卷,第262 - 253页,2010年。视图:出版商的网站|谷歌学术搜索
21. 问:妞妞,b .焦和x顾,“粒子群优化结合遗传算子对模糊作业车间调度问题处理时间,“应用数学和计算,卷205,不。1,第158 - 148页,2008。视图:出版商的网站|谷歌学术搜索
22. c . r . j .朋地船帆座,gonzalez rodriguez,“快本地搜索模糊作业车间调度,”2010年ECAI学报》上IOS出版社,页739 - 744年,里斯本,葡萄牙,2010。视图:谷歌学术搜索
23. 杨绍明。关铭郑,y。李,D.-M。Lei,“群附近搜索模糊作业车间调度,“国际期刊创新的计算和应用,3卷,不。3、144 - 151年,2011页。视图:出版商的网站|谷歌学术搜索
24. j .问:李x和y锅”,混合离散粒子群优化算法求解模糊作业车间调度问题,“国际先进制造技术杂志》上,卷66,不。1 - 4、583 - 596年,2013页。视图:出版商的网站|谷歌学术搜索
25. 杨绍明。关铭郑,y。李,“人工蜂群算法模糊作业车间调度,“国际期刊的计算机应用技术,44卷,不。2、124 - 129年,2012页。视图:出版商的网站|谷歌学术搜索
26. Ben Hmida a . m . Haouari蔡明俊。女人,p·洛佩兹,“差异寻找柔性工作车间调度问题,“电脑与行动研究,37卷,不。12日,第2201 - 2192页,2010年。视图:出版商的网站|谷歌学术搜索|MathSciNet
27. y元,h .徐”,一个集成的启发式搜索大型柔性工作车间调度问题,“电脑与行动研究,40卷,不。12日,第2877 - 2864页,2013年。视图:出版商的网站|谷歌学术搜索|MathSciNet
28. m·a·冈萨雷斯,c . r .船帆座,r . Varela”一个高效的迷因算法的柔性工作车间设置时间,”学报》第23届国际会议上的自动规划和调度,icap 2013,页91 - 99,意大利,2013年。视图:谷歌学术搜索
29. d . Lei“柔性工作车间调度的遗传算法与模糊处理时间,“国际期刊的生产研究,48卷,不。10日,2995 - 3013年,2010页。视图:出版商的网站|谷歌学术搜索
30. g . l . Wang周、y徐和m .刘”混合人工蜂群算法的模糊柔性作业车间调度问题,“国际期刊的生产研究,51卷,不。12日,第3608 - 3593页,2013年。视图:出版商的网站|谷歌学术搜索
31. 徐y l . s . Wang Wang, l . Min”的有效分布估计算法与模糊柔性作业车间调度问题处理时间,“国际期刊的生产研究,51卷,不。12日,第3793 - 3778页,2013年。视图:出版商的网站|谷歌学术搜索
32. d . Lei“协同进化遗传算法模糊柔性作业车间调度,“应用软计算,12卷,不。8,2237 - 2245年,2012页。视图:出版商的网站|谷歌学术搜索
33. d . Lei郭x,“群附近搜索模糊柔性作业车间调度的算法,”国际期刊的生产研究,50卷,不。6,1639 - 1649年,2012页。视图:出版商的网站|谷歌学术搜索
34. j·j·帕拉西奥斯m·a·冈萨雷斯,c·r·贝拉Gonzalez rodriguez,和j .朋地“遗传禁忌搜索的模糊柔性工作车间的问题,“电脑与行动研究54卷,第89 - 74页,2015年。视图:出版商的网站|谷歌学术搜索
35. 杨问:b . Wang, x, x,“健壮的和令人满意的工作车间调度模糊加工时间和灵活的到期日期,”自动化学报2010年IEEE国际会议和物流,第580 - 575页,2010年。视图:谷歌学术搜索
36. m .民宿和l . m . Gambardella“旅行推销员问题的蚁群,”生物系统,43卷,不。2、73 - 81年,1997页。视图:出版商的网站|谷歌学术搜索

版权

版权©2018 Habibeh纳齐夫。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。