考虑患者分类的应急手术调度研究

余梦圆，叶春明，赵灵玮，郭 静，马 琨

上海理工大学 管理学院，上海 200093

调度理论在生产车间、车辆等领域已经得到广泛应用，但在应急救援管理中还需要不断完善与创新。城市突发公共卫生事件，指的是在城市中由于无法进行提前预测或者未能准确检测而突然发生的，涉及广大人民群众的生命生活全方面，并可能会带来实际损失的事件。它的主要特点是突发性、范围广、传播快、信息局限、复杂性、难以预测、破坏性等。城市突发事件一旦发生，对国家的政治和经济都会造成不可估量的影响，甚至还会威胁到社会的稳定。距离最近的就是2019新型冠状病毒，这种病毒传染极快，特别是在人群聚集的地区。手术调度问题是各种调度问题中的热点问题，并在患者救治方面有着直观作用，多年来国内外很多学者都对其进行研究。

传统的手术调度问题假设患者的手术持续时间是固定的，即在调度开始之前就预先知道了所有患者的手术持续时间并基于此进行排序与优化[1]。但是，在实际应急手术情形下，患者手术时间会随着手术开始时间的延长出现手术效率下降的情况，具体表现为针对同一患者，越晚开始手术，其所需要的手术时间就越长。相对应的，对于疫情手术的相似性，医护人员能够在手术进行中对手术过程更加熟练，从而对于后进行手术的患者，会缩短部分手术时间。

目前，手术调度管理针对以下问题：人力、社会、资源、信息等资源的冗余或匮乏；医生连续工作产生疲劳；手术室开放时间不足或过剩；完成时间太迟；医生长时间加班、医疗设备空闲、病患等待成本过高等。学者们以手术时间、院方及患者期望收益、取消风险、患者满意度、综合成本和可信度等为目标，建立符合医院实际情况的模型，并寻求模型的最优解。Anne等[2]提出每个病人同等重要，通过调度手术组患者，来减小手术后住院床位占用率的可变性，并采用禁忌搜索算法求解，发现该模型适合短期住院病人。提出可使用计量经济学模型预测病人状况，病人的年龄、性别、外科医生和疾病是可以区分病人手术时间的一些变量。王腾飞等[3]以等待成本、加班成本和空闲成本为目标，通过蒙特卡洛方法转化为混合整数规划模型，对日间手术预约调度问题进行研究并进行敏感度分析。Paola等[4]在主手术调度背景下，根据三个性能标准采用不同调度策略，探寻效率、平衡和稳健性的价值。Lisa等[5]通过混合研究方法，找出了影响实时手术安排的不确定性因素，提出弹性手术安排的框架。安佰玲等[6]给出了病床合理安排的三个评价指标，建立非线性优化模型，结合蒙特卡洛方法进行模拟求解。潘兴薇等[7]考虑两种类型的检查的不同需求，并考虑患者两类紧急程度和患者的失约，进行门诊患者调度研究。

近年来，许多学者对布谷鸟算法进行了研究，并应用于多种情境。Dipak等[8]将布谷鸟搜索算法中的连续位置转换为离散的调度问题，以最长加工时间为目标验证了并行机调度的有效性。Hamidreza等[9]提出了多目标入侵杂草优化算法对布谷鸟算法改进，并评价多技能资源约束项目调度问题，最后采用基于优先级的方法对所提出的算法进行了不同指标的比较。Preetam等[10]提出了一种离散种间的布谷鸟搜索算法，采用最小位置值法，并进一步说明了其在解决混合流水作业调度问题和置换流水作业排序问题中的优越性。

手术调度是应急救援管理的重要问题，是优化医院医疗资源与服务的关键环节之一。在医院日常运行中，或许并没有大批患者短期内到达，但在应急救援中，通常会有大量患者等待救治。上述文献在多角度对手术调度做了有效研究，为后续的研究奠定了良好的基础，但是这些研究都没有考虑患者的分类对手术调度的影响。因此本文考虑不同的患者类型，并同时考虑手术团队的学习效应和患者伤情的恶化效应，在新冠疫情的背景下，对应急手术调度问题展开研究。

1 应急手术调度模型

1.1 问题描述

本文研究的是城市公共卫生事件发生后，伤员到达救助医院后应急手术救治过程。手术调度的过程可以看作是三级混合流水车间问题[11]，分为术前准备阶段（预麻醉）、手术阶段和手术恢复阶段（麻醉恢复）。国内大型医院的恢复室数量与手术室数量相近[12]，因此只有恢复阶段有空余时，患者才可以被转送去术后恢复室，否则要在当前的手术室滞留，直至有空余的恢复室。若手术调度不合理，将会直接导致手术室和恢复室的利用率低下，最终导致患者得不到妥善及时的救治与安排。手术具体流程如图1所示。

将在医院或者应急救援点的患者，按照术前麻醉—手术—术后恢复的流程，建立多目标整数规划模型。在此情景下，将患者按照手术服务时间长短和伤情紧急程度相结合的方式进行手术调度，基本变量表述如下：

n位患者pi(i=1,2,…,n)将在m(m=3)道手术工序上依次进行手术治疗，所有患者的手术流程相同；Oij表示第i位患者的第j道手术工序；mj(j=1,2,…,m)表示第j道手术工序包含的手术室数量，每位患者都可以在某一手术阶段的任意手术室，且每位患者的手术治疗路径彼此独立；tijk表示患者i在第j道手术工序的第k间手术室进行手术的时间；Sij表示手术工序Oij的开始时间；Cij表示手术工序Oij的完成时间；Ci表示患者i的整个手术完成时间；Njk表示第j道手术工序的k间手术室治疗的患者数量；xijk为0、1变量，若Oij选择在第k间手术室进行手术则为1，否则为0。

1.2 患者分类手术室选择

在大规模城市突发公共卫生事件的背景下，患者的伤情具有高度的相似性，为提高手术治愈率，针对患者的不同伤情，将病患的种类分为三级。在术前对患者进行有效分类可以极大程度减少伤亡，并提高医生的手术效率。用pu表示分类患者的集合，分为轻度患者p1、重度患者p2、危重患者p3,易知p1+p2+p3=n；表示在第j道手术工序的手术室k上救治的第R个u类患者。在手术的准备阶段和恢复阶段，三类患者在任意一间都可以得到合理的救治，而在手术阶段却不一样。医院一般采用r1（30 m2）和r2（50 m2）两种规格的手术室对患者进行救治，其中危重患者由于手术过程的复杂性及人员和设备的多样性，只能选择在50 m2的手术室进行手术，而轻度患者和重度患者在两种手术室都能完成手术。

表1 分类患者手术室选择Table 1 Selection of operating room for classified patients

因此，重症患者p3在手术阶段在特定手术室进行可以表示为：

式中，gij是决策变量，表示第i位患者的第j道手术工序是否必须在某类指定的手术室进行手术，若是，其值为1，否则，其值为0。

1.3 手术团队学习效应与患者恶化效应

在城市公共卫生突发事件中，患者常因得不到及时治疗而使病情恶化，因此应急救援尤为重要，更何况大部分患者往往拥有相似的病情，处理手段也具有一定的相似性。手术时间不是固定的，这取决于正常手术时间、手术顺序、手术团队积累的经验、控制参数及其开始时间。在实际的时间表中，手术时间会随着手术团队经验的积累而呈现一定程度的减少，这就是学习效应[13]。随着处理手术的数量增多以及手术时间的累积，负责固定手术阶段医生的经验越来越丰富，技术越来越成熟，因此手术救治过程拥有一定的学习效应[14]。手术团队的学习效应指的是由于手术过程的重复性，医疗团队进行重复操作而获得手术救治经验的积累，使得继续救治同一类患者时，手术时间不断下降，患者的手术救治效果更好的过程。与此同时，患者不同的等待手术时间也会带来恶化效应，因此实际手术所用的时间表示为：

式中，C′i1,C′i2,…,C′im分别为患者i的第j道手术工序实际结束时间；ti1k,ti2k,…,timk分别为基本手术的各个工序所需时间；α1,α2,…,αm分别为医护工作者不同手术阶段的学习系数；βi(0≤βi≤1)表示第i位患者的恶化系数。

1.4 目标函数

本文根据对手术调度实际情况的分析，确定的调度目标集表示为min(f1,f2,f3)。其中f1表示平均手术时间；f2表示患者恶化成本；f3表示手术室总能耗。

（1）最小化平均完成手术时间

在医院的手术管理中，很多管理过程都是统一的，例如部分手术室的中央空调是集中进行管控的；手术室的普通照明灯光是统一进行控制的，等等。同时，用最小的时间对患者进行有效治疗是医院和患者同时关注的重点，手术时间在一定程度上也关乎着患者的身体及精神负担。因此，对所有患者的手术过程平均时间的考虑是必要且有效的。

（2）最小化患者恶化成本

患者的恶化成本也是应纳入考虑的重要因素，在最佳治疗时间内进行手术能极大降低患者进一步恶化的风险，手术开始和进行的时间与患者的治愈效果直接相关，靠前则治疗效果相对较好，反之亦然。因此，患者的恶化成本包括手术开始前等待时间成本和手术持续时间成本。

式中，参数ω、δ1、δ2、δ3为非负数。

（3）最小化手术室总能耗

Karme等[15]提出手术完成质量与执行或推迟手术、手术室加班和闲置时间以及重症监护室（ICU）的成本不足有关。Wim等[16]提出资源过载的数量是进行评估的重要因素，并针对医院的资源对手术数量进行研究，结果表明构建的模型在文献和实践中考虑的许多外科病例调度方面有较好的改进效果。

在应急救援管理中，由于突发事件的随机性和广泛性，医疗消耗资源例如医用外科口罩、防护服和检验类试纸等是有限的，资源的调度需要一定的时间，未必能按时按量送达指定地点。同时手术所需的各类医疗设备，例如呼吸机、制氧机、麻醉机和X射线机等，它的能耗越小，则设备的损耗越小，越能救治更多的患者，同时医疗成本也越低。因此，医院进行手术的资源在应急管理的场景下是珍贵的，对资源有效合理地利用能在一定程度上提高手术的效率、患者的治愈率以及患者的救治数量。本文将医院的手术资源量化为手术室的总能耗进行研究。

综上所述，手术室总能耗也是应急手术考虑的重要因素，其包括忙时能耗和空载能耗，手术过程中的能耗与调度方案直接相关。手术室处于空载状态时会加速医疗设备的老化，以及手术室能源包括空调在内的无故消耗。同样，手术室作业时也会加速设备的老化，同时也会消耗医院的医护资源和医疗用品资源等。因此，手术室总能耗的计算公式为：

式中，IEk表示手术室k上的单位时间空载的单位能耗；Tk表示手术室k处于空载的时间；PEijk表示手术工序Oij在手术室k处于忙时的单位能耗。

1.5 应急手术调度数学模型

本文以平均完成手术时间、患者恶化成本和手术室总能耗为目标，对应急手术调度进行优化研究。为了简化并构建合理有效的模型，需要对问题做出如下假设：

（1）一间手术室同一时间只能进行一台手术；

（2）一位患者同一手术阶段只能在一间手术室进行；

（3）保证手术过程连续性，一旦开始就不能中断；

（4）手术过程必须按照同一顺序依次进行；

（5）不考虑手术过程中突发情况手术间转移情况；

（6）不同患者之间没有先后约束；

（7）手术过程中患者的移动时间忽略不计；

（8）手术过程中所有资源包括人员、设备和物资准备充足并且能够准时到位；

（9）患者的类别已全部分好，不存在检查产生的时间；

（10）没有特殊要求的病患，并且在手术前不用特殊检查[17]；

（11）所有手术的初始开始时刻以及手术间的开始手术时间都为0；

（12）不考虑连续不同手术之间的切换时间。

约束条件如式（6）～（15）所示：

式（6）表示每位患者在同一手术工序上只能在唯一的手术室进行治疗；式（7）和式（8）表示应急手术每个阶段至少有一个病床；式（9）表示每道手术工序治疗的患者总数为n；式（10）表示一间手术室在同一时间只能对一位患者进行一道手术过程；式（11）表示必须按照手术流程进行手术；式（12）表示手术过程Oij一旦开始就不可以中断；式（13）表示手术工序的顺序约束；式（14）约束了手术开始和结束时间一定是正数；式（15）表示变量的取值范围。

2 算法设计

2.1 应急手术调度数学模型

布谷鸟算法（cuckoo search，CS）是由英国剑桥大学的Yang等在2009年提出的一种仿生群智能算法[18]，是一种求解优化问题的新型高效的基于种群的启发式进化算法，具有实现简单、控制参数少等优点。该算法是基于某些布谷鸟类的义务后代寄生行为，结合某些鸟类和果蝇的Lévy飞行行为而设计的。该算法的灵感来源于布谷鸟的繁殖策略，根据布谷鸟产卵时的飞行机制进行搜索，能够快速有效地解决多维空间寻优问题。通过模拟布谷鸟的智能繁殖行为而开发出来的，基于群体的搜索过程，作为优化工具，解决复杂的、非线性的和非凸的优化问题。在初始化过程中，所有的鸟巢（解）都是在上限和下限内随机生成的。

2.1.1 Levy飞行

布谷鸟算法的一个重要特征是使用了Levy飞行的方式进行局部和全局搜索。Levy飞行过程，以前被用于其他启发式搜索，其特征是从概率密度函数中选择一系列瞬时移动。这个过程代表了最佳随机搜索模式，在自然界中经常发现[19]。Levy飞行的原理是模拟一种随机游走过程，它由低频率的长距离飞行和高频率的短距离飞行所组成，其步长服从Levy分布。因此，布谷鸟算法寻找鸟巢的位置以及路径更新公式如下：

式中，Xti为当前的解；⊗为点乘；Levy(λ)为Levy飞行的搜索路径；λ为参数；α是步长参数，其大小直接取决于问题的规模，具体可表示为：

式中，α0为大于0的实数，通常取0.01；Xbest表示当前最优解。

2.1.2 布谷鸟搜索过程

传统的布谷鸟算法需要满足以下三种原则：（1）布谷鸟随机选择寄生巢，并且随机产卵。（2）只有拥有最高质量的卵的最好的巢才会被选择给下一代。（3）布谷鸟的卵被宿主察觉的概率为pa，并且被察觉后，布谷鸟需要寻找新的鸟巢。最后一个假设可以理解为：如果参数设置为0.2，则在每次迭代结束时，有20%的最差巢穴将被随机生成的新巢所取代。Levy飞行表示随机飞行的路径，飞行的方向服从均匀分布，连续跳跃距离和时间t服从著名的Levy概率分布，故对其简化和进行傅里叶变换后，得到符合幂次形式的分布：

式中，u是一个带有重尾的概率分布，服从Levy分布，该分布有一个无穷方差和无穷均值，其步长本质上构成一个随机行走过程。

2.2 改进的布谷鸟算法

布谷鸟算法具有全局搜索性能好、参数较少、简单易实现等优点。但它只适用于局部，容易陷入局部最优解，并且最初的布谷鸟算法是为了应用于连续优化问题而开发的。因此，该算法不能直接用于解决离散的问题，通过改变算法的原始范式，将算法的思想推广到离散域。

2.2.1 Levy飞行数学模型

本文采用Mantegna[20]提出的Levy飞行算法，公式如下：

式中，θ为分布参数，θ∈[0.3,1.99]，一般取1.5；μ和v服从正态分布，μ:N(0,σ2μ)和v:N(0,σ2v)；σμ和σv的取值如下：

综上所述，布谷鸟算法的位置更新公式为：

2.2.2 被发现概率自适应调整

传统的布谷鸟算法都会采用不变的被发现概率pa，并且一般取值为0.25。被发现概率的大小会直接影响寻优的搜索速度，若被发现概率过大，则会较难收敛到最优解并有可能陷入局部最优；而过小，则会使得收敛速度较慢并对搜索范围盲目搜寻。因此，为了解决该问题，本文引入自适应调整机制，具体如下：

式中，pmax表示最大被发现概率；i表示当前迭代次数；Max_iter表示最大迭代次数；pmin表示最小被发现概率。

该策略使得算法在计算前期保证全局搜索能力的前提下快速收敛到非劣解，随着迭代次数的逐步增加，种群个体的质量也随之增高。到了计算后期，被发现概率会随着迭代次数的增加而递减，有利于算法进行更精确的局部搜索。相比于其他改进方式，本文提出的改进策略参数少，求解速度快，实现方式简单，有效地改善了搜索能力和收敛速度。

2.3 编码规则

编码是算法实现的关键。由于患者手术排序编码是离散型的，无法直接使用布谷鸟算法，本文需要对手术工序和手术室进行编码。考虑当前手术工序手术室选择和患者前后手术顺序两方面，为此，本文设计一种同时考虑当前患者手术选择和患者前后手术顺序的两段式整数编码方式，如图2所示。

基于手术工序编码中，数字表示患者编号，数字出现的次数表示手术工序，比如第三个数字1表示患者1的第2道手术工序。基于手术室编码中，上行数字表示手术室编号，比如说第三个数字5表示患者1的第2道手术工序在手术室5上进行。第一段编码确定患者手术工序的顺序，第二段编码确定当前患者手术工序所在的手术室。两段编码相结合确保所求解可行。

2.4 算法步骤

综上所述，改进的布谷鸟算法对应急手术调度问题具体实现步骤如下：

步骤1设置算法参数，被发现概率pa，编码上下限，Pareto解的个数Z，设置搜索终止条件以及最大迭代次数Max_iter。

步骤2初始化种群，计算各个鸟巢的目标函数值，并保留最好鸟巢及其目标函数值。

步骤3计算鸟巢位置，对应三个目标函数值，构建初始Pareto最优解集。

步骤4根据位置更新公式（16）～（21），得到下一代鸟巢的位置。

步骤5计算每个鸟巢的目标函数值，并与上一代的鸟巢进行对比，如果较优，则更新当前最好鸟巢的位置和最优目标函数值。

步骤6用随机游走的方式产生的新鸟巢代替位置较差的部分鸟巢，并计算被发现概率pa；每个新鸟巢产生一个随机数r，服从[0,1]之间均匀分布，如果r大于被发现概率pa则返回步骤4，否则进入步骤7。

步骤7比较两代鸟巢目标函数值，构建新Pareto最优解集，并计算每个鸟巢的目标函数值，更新最优鸟巢。

步骤8判断当前迭代次数是否达到最大迭代次数Max_iter，若不符合则返回步骤4；否则终止算法，输出Pareto解。

改进后的算法流程图如图3所示。

3 仿真实验

3.1 算例描述

在新冠肺炎疫情的背景下以某地突发城市公共卫生事件为例，验证本文提出的模型和设计的布谷鸟算法。假设突发事件后有12个患者需要应急手术，所有患者全部同时到达[21]，患者的伤势人数比例为轻度患者50%、重度患者25%、危重患者25%。患者都需要依次进行准备、手术和恢复3个手术流程，手术不同阶段手术团队的学习率分别取20%、15%和10%；患者恶化率取1.5%。其中，准备室有2个编号为m1、m2；手术室有5个，包括3个r1手术室编号为m3、m4、m5和2个r2手术室编号为m6、m7；恢复室有3个编号为m8、m9、m10。成本参数设置方面，文静等[22]在急诊检查调度研究中考虑了患者的滞留成本，与本文的患者因长时间等候造成的恶化成本相似，因此将参数一致设置为ω=1/15,δ1=0,δ2=1,δ3=2。手术室能耗参数方面，于思文[23]在对手术排程研究中的手术室加班和空闲的惩罚系数的值是以Jebali[24]研究中的系数为标准，因此设定各手术室单位时间的空载能耗系数IE=1,手术室处于忙时单位时间的能耗系数PE=8[25]。手术时间具有不确定性的特点，同时考虑患者的不同分类，患者在每个手术流程的具体治疗时间如表2所示。

表2 患者在每个手术室的治疗时间Table 2 Treatment time of patients in each operating room 单位：min

3.2 结果及分析

多目标应急手术调度问题求解的运行环境为：操作系统为Windows10，处理器为Intel®CoreTMi5-5200U，主频为2.20 GHz，内存为4 GB，采用MatlabR2018a编程实现。

根据应急手术调度的数学模型，将改进的布谷鸟算法与传统的布谷鸟算法的运行结果进行对比。为了验证算法的有效性，设置算法的总迭代次数为100，分别对两组实验独立运行20次后取平均值，实验结果具体如表3所示。从表3可以看出，与传统的布谷鸟算法相比改进的布谷鸟算法对目标函数f1有15.51%的提升；对目标函数f2有30.72%的提升；对目标函数f3有15.52%的提升。这说明经过被发现概率自适应性调整的布谷鸟算法能够很好地找到Pareto解，并避免陷入局部最优。

表3 20组Pareto最优解Table 3 20 Pareto optimal solutions

为了更清楚地看出改进布谷鸟算法的收敛速度，本文随机选取表3中的第17次运行过程，绘制算法的收敛曲线图。平均完成手术时间、患者恶化成本和手术室空载及忙时总能耗三个目标函数的迭代曲线具体如图4所示。图中横坐标表示迭代次数，纵坐标表示各目标函数的变化值。

从图4可以看出，随机选取的第17次运行结果的最优目标值收敛曲线中改进的布谷鸟算法相比传统布谷鸟算法，具有更快的收敛速度。

由此绘制的甘特图如图5所示，图中横坐标表示时间；纵坐标表示不同手术室，图中不同颜色代表不同患者，并且每个患者应急手术不同阶段的颜色是相同的。图5中患者手术的三个阶段在时间维度上基本首尾相接，说明患者的应急手术调度安排得比较紧凑，调度结果比较合理。

根据图6可知，Pareto可行解的分布比较分散且均匀，能够有效地跳出局部收敛状态，说明被发现概率自适应性能够使布谷鸟算法跳出局部最优，扩大搜索的范围，有效更新鸟巢并保证种群的多样性。

3.3 不同参数对手术调度的影响

手术团队中各成员直接配合的默契程度以及医生的职称和经验之间存在差异，会有不同的学习效应，学习率以20%、15%、10%为例，按照手术阶段依次递减规律，独立运行改进的布谷鸟算法20次求平均值，以平均手术时间为例，结果如表4所示。由表4可知，随着不同手术阶段的学习率的递减，平均手术时间并不是直线下降而是呈现跳跃的趋势。

表4 不同学习率下的调度结果Table 4 Scheduling results under different learning rates

由于每批患者的恶化效应存在差异，会导致患者拥有不同的恶化效应，恶化率分别取0.5%、1.0%、1.5%、2.0%、2.5%、3.0%，独立运行改进的布谷鸟算法20次求平均值，同样以平均手术时间为例，结果如表5所示。由表5可知由于恶化率的存在，应急手术调度问题的所有患者平均完成手术的时间会比理论值小，并且恶化率越高，对手术调度的结果影响越大。

表5 不同恶化率下的调度结果Table 5 Scheduling results under different deterioration rates

4 结束语

应急手术的调度对患者伤势的救治情况起着至关重要的作用。本文充分考虑手术治疗的三个阶段与三级置换流水车间相似的特点，将流水车间的思想运用到应急手术调度中，以最小化平均完成手术时间、患者恶化成本和手术室总能耗为目标，并同时考虑了患者的三级分类。在求解算法方面，对算法中被发现概率进行自适应性调整，通过对算法和模型的结果分析，验证了改进布谷鸟算法的有效性。未来可进一步考虑突发事件不同阶段的特征，针对性地探索手术资源及医院资源多周期配置，进行动态手术调度研究。