本文研究多服务台手术计划调度问题，考虑手术时间的不确定性，提出手术室加班时间的机会约束，以一定的概率保证病人的手术时间不超过手术室的开放时间，建立随机优化机会约束手术计划调度模型，确定手术室的开放和分配决策.基于手术时间离散的概率情景，引入0-1变量转化机会约束，得到了0-1整数线性规划的等价模型.为了提高模型的求解效率，提出两类有效不等式，并设计最长路径算法分离第二类有效不等式，利用分支切割方法进行模型求解.算例分析，基于北京某医院的实际数据，验证算法的有效性，确定最优的手术计划调度方案，有效地优化配置手术室资源.
Abstract
To address the uncertainty of surgery duration, this paper investigates surgery planning scheduling problem with multiple servers, which proposes chance constraints of operating rooms overtime to guarantee the surgery durations of patients is no more than the time limit of operating rooms with a high probability. A stochastic chance-constrained program is proposed to determine which operating rooms to operate, and surgeries to operating rooms allocation. Based on a finite support set of the surgery duration, this paper introduces 0-1 variables to formulate the chance constraints, and derives 0-1 integer linear program counterpart. To improve the efficiency of the model, this paper presents two classes of valid inequalities and uses the longest path algorithm to separate the second class of valid inequalities, which are implemented in a branch-and-cut framework. Computational experiments based on real-life data from hospital in Beijing are conducted to verify the algorithm performance and determine the optimal planning scheme, so as to take full utilization of healthcare resources, i.e. operating rooms.
关键词
手术计划调度 /
机会约束 /
分支切割 /
有效不等式 /
分离算法
{{custom_keyword}} /
Key words
surgery planning and scheduling /
chance constraint /
branch-and-cut /
valid inequalities /
separation algorithm
{{custom_keyword}} /
中图分类号：
O224
F224
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 王昱, 唐加福. 医院手术调度问题的两阶段鲁棒优化方法研究[J]. 系统工程学报, 2016, 31(4):431-440.Wang Y, Tang J F. A two-stage robust optimization method for solving surgery scheduling problem[J]. Journal of Systems Engineering, 2016, 31(4):431-440.
[2] 彭春, 李金林, 王珊珊, 等. 考虑下游ICU病床容量约束的鲁棒手术计划调度[J]. 系统工程理论与实践, 2018, 38(3):623-633.Peng C, Li J L, Wang S S, et al. Robust surgery planning and scheduling with downstream bed capacity constraint in ICU[J]. Systems Engineering-Theory & Practice, 2018, 38(3):623-633.
[3] Zhang F Y, Luo L, Liao H C, et al. Inpatient admission assessment in West China Hospital based on hesitant fuzzy linguistic VIKOR[J]. Journal of Intelligent & Fuzzy Systems, 2016, 30(6):3143-3154.
[4] Luo L, Liu H J, Liao H C, et al. Discrete event simulation models for CT examination queuing in West China Hospital[J]. Computational and Mathematical Methods in Medicine, 2016. http://dx.doi.org/10.1155/2016/2731675.
[5] Liao H C, Zhang C, Luo L. A multiple attribute group decision making method based on two novel intuitionistic multiplicative distance measures[J]. Information Sciences, 2018. doi:10.1016/j.ins.2018.05.023.
[6] 陈乐天, 耿娜, 祝延红, 等. 基于仿真优化算法的医院关键资源能力分派研究[J]. 运筹与管理, 2018, 27(2):38-47. Chen L T, Geng N, Zhu Y H, et al. Simulation-based optimization for capacity allocation of critical resources in the hospital[J]. Operations Research and Management Science, 2018, 27(2):38-47.
[7] Zhu S, Fan W, Yang S, et al. Operating room planning and surgical case scheduling:A review of literature[J]. Journal of Combinatorial Optimization, 2018:1-49.
[8] Denton B T, Miller A J, Balasubramanian H J, et al. Optimal allocation of surgery blocks to operating rooms under uncertainty[J]. Operations Research, 2010, 58(4-part-1):802-816.
[9] Erdogan S A, Denton B. Dynamic appointment scheduling of a stochastic server with uncertain demand[J]. INFORMS Journal on Computing, 2013, 25(1):116-132.
[10] Molina-Pariente J M, Hans E W, Framinan J M. A stochastic approach for solving the operating room scheduling problem[J]. Flexible Services and Manufacturing Journal, 2018, 30(1-2):224-251.
[11] Gul S, Denton B T, Fowler J W. A progressive hedging approach for surgery planning under uncertainty[J]. INFORMS Journal on Computing, 2015, 27(4):755-772.
[12] 邓富民, 梁学栋, 刘爱军, 等. 多资源约束下改进NSGA-Ⅱ 算法的手术调度[J]. 系统工程理论与实践, 2012, 32(6):1337-1345.Deng F M, Liang X D, Liu A J, et al. Surgical operation scheduling with multi-resource constrained based on the improved NSGA-Ⅱ algorithm[J]. Systems Engineering-Theory & Practice, 2012, 32(6):1337-1345.
[13] Luedtke J, Ahmed S. A sample approximation approach for optimization with probabilistic constraints[J]. SIAM Journal on Optimization, 2008, 19(2):674-699.
[14] Song Y, Luedtke J R, Küçükyavuz S. Chance-constrained binary packing problems[J]. INFORMS Journal on Computing, 2014, 26(4):735-747.
[15] Deng Y, Shen S. Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints[J]. Mathematical Programming, 2016, 157(1):245-276.
[16] Wang S, Li J, Peng C. Distributionally robust chance-constrained program surgery planning with downstream resource[C]//2017 International Conference on Service Systems and Service Management (ICSSSM), IEEE, 2017:1-6.
[17] Atamtürk A, Nemhauser G L, Savelsbergh M W P. The mixed vertex packing problem[J]. Mathematical Programming, 2000, 89(1):35-53.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金（71432002，71672011）
{{custom_fund}}
PDF(666 KB)
