推文作者信息：张舒政，东北大学管理科学与工程系在读博士生。
研究方向：鲁棒优化、医疗运作管理。
编者按
患者特征如性别、年龄和基础病对提高手术调度模型的准确性至关重要。本文研究了结合患者特征的鲁棒手术调度问题，聚焦于择期及急诊患者的手术室分配。利用特征数据，通过机器学习方法将患者分类，并基于特征聚类构建模糊集以描述手术时长的不确定性。本文提出了一个特征驱动的自适应鲁棒优化模型，旨在最小化超时风险指数，以同时降低加班的幅度和概率。该模型可重构为二阶锥规划问题。重构后发现，最小化超时风险指数等同于最小化Fano因子。为高效求解，开发了branch-and-cut算法并引入打破对称性的约束。数值实验表明了方法的性能优势。
参考文献：Wang Yu, Zhang Yu, Zhou Minglong, Tang Jiafu. (2023). Feature-driven robust surgery scheduling. Production and Operations Management, 32, 1921–1938.
1. 研究背景
随着社会经济的持续发展及人口老龄化趋势的加剧，医疗需求显著上升，部分高级别医院，特别是三级甲等医院，面临医疗资源供需失衡的挑战。据国家统计局数据显示，自2013年至2023年间，手术量从3982万例激增至8271万例，翻了一番有余。为有效缓解此矛盾，国家采取了一系列措施，其中，提升手术调度的效率与精准度，优化手术资源配置已成为重要策略之一。
手术调度问题作为医院运营管理的重要组成部分，其核心在于如何高效、公平地分配有限的手术室资源。在我国医疗体系中，手术室通常保持全天候开放状态，因此调度决策主要聚焦于患者分配。患者群体可细分为择期手术患者与急诊手术患者两类。前者手术需求可预知，便于提前规划；而后者则具有突发性和不确定性，其出现时间及手术需求难以提前精确预测，增加了调度的复杂性。
手术调度的核心任务在于，基于不精确的手术时长预估（实际手术时长常偏离预期），将患者科学合理地分配至各手术室，同时力求减少加班现象。手术加班不仅导致医疗成本攀升（如高额加班费支出），还可能引发财务损失，加剧医护人员与患者双方的压力与不满，进一步增加手术风险。因此，构建一个能够有效减少加班、提升整体效率的手术调度系统，显得尤为重要。作为运营管理领域的经典问题，手术调度已吸引大量学者与业界专家进行深入探索与研究。
2. 问题描述
医院手术调度问题核心聚焦于优化手术资源的配置效率，以有效应对高度不确定的医疗需求。患者群体包括需求明确的择期患者与需求突发且难以预测的急诊患者，后者显著增加了调度策略的复杂性和实施的挑战性。手术调度任务的关键在于，将患者合理分配到各个手术室，同时减少因手术时长不确定而导致的加班现象。鉴于加班现象不仅导致医疗成本攀升，还损害医患满意度，加剧医务人员疲劳，并潜在增加手术风险，因此需采取有效措施，控制并减少加班现象，确保医疗服务的高效供给。
本文考虑一个包含个择期患者与个急诊患者的手术调度问题，其中择期患者信息提前可知，而急诊患者的实际到达数量无法提前观测。为应对急诊患者数量的不确定性，本文引入“虚拟患者”（Dummy Patient）概念，若急诊患者未实际到达，则视为手术时长为0的虚拟患者。值基于历史经验设定，旨在反映可能到达的急诊患者最大数量。每位患者的手术时长视为随机变量，以波浪号表示。
给定个手术室及固定的开放时长小时条件下，通过调度决策为所有患者分配手术。决策为0-1变量，可行域要求为每名患者必须安排且仅安排一次手术，表示如下
同时，引入“延迟”（Delay）概念，表示手术室实际手术时长超出其规定开放时长的部分，即延时开放时长。
若延迟为正，则代表加班；若为负，则表示无需加班。
经典的手术调度模型采用最小化期望加班时长作为目标，优化目标为选取，使得期望总加班时长最小化。
该模型有以下难点：
由于患者的异质性，新到达患者的手术时长的真实分布难以准确描述； 传统模型的优化目标仅考虑加班概率或者时长单一指标，无法同时度量加班概率和时长； 急诊患者分配决策需根据急诊患者的特征及到达时系统状态而调整； 计算复杂度与可处理性限制。
为解决上述问题，本文进行了文献回顾。基于以往研究，本文提出了一种新颖的特征驱动的鲁棒优化方法，旨在根据患者特征数据更准确地刻画手术时长分布，以做出适应性决策抑制加班，并优化计算效率，以期为医院手术调度提供更加科学、高效的解决方案。
3. 主要工作
针对上述挑战，本文进行了以下深入研究：
特征驱动的手术时长模糊集：与忽略患者特征信息的研究不同，本文应用机器学习方法从历史数据中提取信息，构建了特征驱动的模糊集，将机器学习与分布鲁棒优化相结合来描述不确定的患者服务时长分布。 加班风险量化：为了全面评估加班风险，本文引入了加班风险指数。这一指数不仅考虑了加班时长，还兼顾了加班发生的概率，具有理论上的概率保证。通过性质说明和实例分析，验证了该指标的有效性和合理性。 患者特征驱动的分布鲁棒优化：本文开发了一个新颖的特征驱动的分布鲁棒优化模型，该模型能够利用患者的特征数据来优化手术室的分配决策。该模型能够自然地描述择期手术和未来可能出现的急诊患者，并且可以找到适应急诊患者身体状况的手术分配方案。同时，本文还证明了该问题的NP难性质，并探讨了其管理学意义和应用价值。 计算可处理性：本文提出的模型可以等价转化为混合整数二阶锥规划模型，设计了Branch-and-cut算法求解该问题，设计了打破对称性等加速策略，确保了算法的高效性和收敛性。
3.1 特征驱动的手术时长聚类模糊集
在信息时代背景下，数据的重要性日益凸显。本文研究基于三甲医院的真实患者数据集。将其部分统计信息绘图如下：
通过运用分类回归树（Classification and Regression Tree, CART）方法，根据患者的特征信息进行了聚类分析，将患者划分为7类，
并计算了每类的分类误差和均值以构建基于患者特征的矩信息模糊集如下
其中符号定义如下
这种基于特征信息的模糊集构建方法，提高了对于患者手术时长刻画的颗粒度，为后续优化调度奠定基础。
3.2 加班风险量化
为全面评估加班风险，借鉴了章宇老师的研究成果，提出了一种新的风险测度指标 Overtime Riskiness Index(ORI)，并将其应用于手术调度领域。
该指标能够同时考虑加班的时长和概率，为决策者提供更为全面的风险信息。例如有三种不同手术分配方案ABC，此时A有50%概率加班10分钟，期望加班时长为5；B有50%概率加班20分钟，期望加班时长为10；C有25%概率25%概率加班40分钟，去期望加班时长为10。仅看期望加班时长和概率都不能直接对三种方案进行比较，此时Overtime Riskiness Index的取值为B>A>C。
此外，该模型还有一些优良的性质，比如凸性和概率界。通过构建合理的性质说明和实例分析，验证了该指标的有效性和合理性。
3.3 急诊患者分配的适应性
针对急诊患者的分配问题，本文设计了一种基于系统状态自动调节的决策机制。该机制允许在急诊患者到达后，根据到达的急诊患者特征（系统状态）调整分配方案。具体来说，当急诊患者到达后，观察其类别为，则其分配方案为，也就是说，该问题得到的是对应着多种系统状态的急诊患者的一系列分配方案。此时问题的可行域如下
这种适应性决策机制不仅提高了调度的灵活性，还降低了因急诊患者到达不确定性带来的风险。此时手术调度模型如下
对其进行对偶转换后，等价于以下问题
此时，该模型有一些管理学上的含义，即该模型的目标相当于
定义松弛时间(slack time)为代表手术室的空闲时间。该模型最小化了所有手术室松弛时间的法诺因子(Fano favtor)之和，并具有管理和经济含义。直观地说，减少松弛时间的方差或增加其平均值可以缓解加班，这一结果使本文的模型易于从管理角度进行解释和论证。
3.4 算法设计与优化
针对上述优化问题，本文提出了基于分支切割的混合整数二阶锥优化算法。该算法通过引入割平面技术，有效处理了复杂的约束条件，确保了算法的高效性和收敛性。
综上所述，本文在手术时长刻画、加班风险度量、急诊患者分配适应性以及算法方面开展了一系列工作。
4. 计算实验
在计算实验中，本文采用了真实数据集以评估所提方法的性能。具体考虑了八个样本外性能指标，涵盖最坏情况下的加班时长、期望加班时长以及加班概率等关键维度。
| 指标 | 含义 |
|---|---|
| WO | 最坏情况下的加班时长 |
| ME | 最大期望加班时长 |
| MET | 超过30分钟的最大期望加班时长 |
| TE | 总期望加班时长 |
| JP | 加班概率 |
| JPT | 加班超过30分钟的概率 |
| TP | 总加班概率 |
| STD | 总加班时长的标准差 |
为验证所提出模型的有效性，将其与两个基准的随机规划（SP）模型进行了对比，这些基准模型基于常见的优化目标。模型缩写及含义如下：
| 模型 | 含义 |
|---|---|
| PS | 最大化按时完工概率模型 |
| ES | 最小化期望加班时长的模型 |
| DRO | 本文提出的模型 |
通过对比分析发现，在关键性能指标上，分布鲁棒优化（DRO）模型展现出了更优的表现，计算实验结果统计如下：
值得注意的是，尽管ES模型专门优化了期望加班这一指标，但本文所提出方法在一定程度上仍表现出更佳的性能。这一现象背后可能的解释是，由于无法确切知悉随机变量的真实分布，仅能依赖有限的历史数据，而实际分布可能具有非平稳性，因此仅凭历史数据推断未来情况可能存在局限性。
此外，就加班概率相关指标而言，PS方法自然表现出最佳性能。尽管如此，本文所提出方法与PS方法之间的差距并不显著，整体性能仍然处于可接受范围内。
5. 结论
本研究聚焦于手术调度问题，通过融合患者特征信息与数据驱动方法，优化患者与手术室的分配策略。特别地，为急诊患者提出了一种特征自适应分配方法。本文构建了一个融合机器学习与运筹学优化技术的数据驱动框架，通过分析揭示了患者特征与手术室利用率之间的内在联系，并为医疗机构提供了关于如何更有效地调度手术资源的理论依据。综上所述，本研究为手术调度领域提供了新的视角和实用的解决方案。
下载原文：https://www.researchgate.net/publication/367098354_Feature-driven_robust_surgery_scheduling
原文作者及信息: 王昱(东北大学)， 章宇(西南财经大学)， 周明龙(复旦大学)， 唐加福(东北财经大学)，Feature-driven robust surgery scheduling. Production and Operations Management, 2023, 32, 1921–1938.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：张舒政
责任编辑：蔡君洋
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
