基于分支定价的手术计划调度研究

摘要

随着国民收入水平的提高和医疗保健意识的增强，广大居民对于医疗服务的需求急速提升。手术室是为病人提供手术及抢救的场所，在整个医院中设备最昂贵，收入最高，动用人力资源最广泛，牵扯到的上下游部门最多。由于手术室中存在诸多的不确定性，如何制定科学、合理的手术计划已成为困扰手术室管理者多年的问题。
　　在手术计划调度中通常考虑两类病人：急诊病人和择期病人。急诊病人随机到达，需要尽快手术；择期病人在医院中等待，可以预先安排手术实施时间。随机到达的急诊病人会对择期病人的手术计划造成消极影响，如手术延迟、取消。现实情况中，拒绝或推迟急诊病人的手术往往会造成病人病情恶化、不满等不良影响。为此，手术室管理者会预留一部分的手术能力以应对随机到达的急诊病人。预留不足会导致急诊病人的手术等待时间过长，预留过剩又必然会造成手术室资源的浪费。
　　为改善这种状况，本文在急诊病人和择期病人共享手术室的前提下，研究急诊病人手术需求随机下的手术计划调度问题，确定一个决策周期内的择期病人手术计划以优化手术室的期望超时成本和期望闲置成本。首先对该问题进行数学描述，建立0-1整数规划模型。鉴于该问题为NP-难问题，设计精确型的分支定价算法求解该问题。首先运用Dantzing-Wolfe分解原理将原始0-1整数规划模型分解为集合覆盖主问题模型和子问题模型。针对子问题模型和背包问题模型的相似性，对子问题进行分解转化后，为子问题的求解设计高效的动态规划算法。通过列生成求解主问题的线性松弛最优解，当松弛解为分数时，利用分支定价算法进行分支搜索找到问题的整数最优解。分支定价算法外层是分支定界法，通过对比几种常用的策略，选择最不可行优先作为分支策略，结合深度优先和最优下界优先的混合策略作为节点选择策略，从而完全搜索解空间以找到整数最优解。数值实验表明，本文提出的分支定价算法可以有效的求解到实例规模问题的最优解。
　　本文研究在理论层面，对考虑随机急诊病人的手术计划调度问题的模型构建和求解具有一定参考价值。在实践层面，可以为手术室管理者提供科学的决策参考。

目录

声明

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 论文组织结构

2 理论基础

2.1 列生成

2.2 分支定界算法

2.3 分支定价算法

2.4 本章小结

3 随机急诊下的手术计划调度问题

3.1 问题描述

3.2 整数规划模型

3.3 集合分割主问题模型

3.4 子问题模型

3.5 本章小结

4 模型求解及数值实验

4.1 列生成

4.2 分支定价算法

4.3 数值实验

4.4 本章小结

结论

参考文献

攻读硕士学位期间所参加的科研项目

攻读硕士学位期间发表学术论文情况

致谢