两阶段鲁棒优化：解决择期手术及下游资源调度难题

需积分: 9 196 浏览量更新于2024-07-20 收藏 3.1MB PDF 举报

本文主要探讨了在复杂且具有多重不确定性来源的手术安排问题中，采用两阶段鲁棒优化方法来解决下游手术排程和资源规划的问题。研究关注的是 elective surgery（择期手术）的安排，这种类型的手术通常需要综合考虑手术持续时间、术后留院观察时长（即ICU长度-Stay, LOS）以及这些不确定因素对下游手术室和ICU等资源的需求。在第一阶段，作者提出了一种鲁棒优化模型，目的是设计一个对 Surgery Duration 和 Length of Stay 的不确定性有抵御能力的手术计划。这种模型考虑了决策依赖的不确定性，即手术安排会影响到后续步骤的资源需求，因此在制定计划时需要对可能的变化进行适应。两阶段优化策略的具体流程如下： 1. **预计划阶段**：在这个阶段，通过考虑当前的信息和预测数据，建立一个基础的手术安排方案。模型旨在确定每个手术的初步时间表，同时最小化不确定性带来的潜在负面影响，如过度预订或空闲资源。 2. **调整阶段**：在实际执行过程中，基于手术进程中的实时信息更新，进行优化调整。这一步可能涉及到对原计划的微调，以应对手术持续时间延长或患者恢复速度超出预期等情况，确保下游资源的合理利用。 3. **鲁棒性保证**：关键在于模型设计的鲁棒性，即即使面对手术持续时间和LOS的未知变化，也能保证整体系统的稳定性和效率。通过引入适当的缓冲区或灵活性，计划能够抵抗一定范围内的不确定性冲击。 4. **应用背景**：研究发表于《欧洲运筹学杂志》(European Journal of Operational Research)，是OR in Health Services (卫生服务中的运筹学)领域的重要贡献，反映了医疗资源管理中的实践挑战和理论发展。 5. **结论与未来方向**：本文的成果有助于医疗机构优化手术排程，降低风险，并提高资源使用效率。未来的研究可能进一步探索多目标优化、动态调整策略，以及与其他决策支持工具的集成，以实现更精确和灵活的手术计划。这篇论文提供了一种创新的框架，将鲁棒优化理论应用于手术排程，旨在解决医疗系统中的复杂决策问题，具有显著的实际应用价值。

24 S. Neyshabouri, B.P. Berg / European Journal of Operational Research 260 (2017) 21–40

Additionally, RO methodology provides means to obtain solutions

that are protected against uncertainty. This characteristic is of

particular interest in health care settings like surgery planning

since the outcome of not considering these sources of uncertainty

can have a serious impact on the health outcome of the patients.

RO provides decision-makers with high quality solutions that,

while minimizing the operating costs, guarantee a high level of

safety and quality of care for patients. The use of cardinality-

constrained uncertainty sets in health care settings and their

beneﬁts and drawbacks are considered by Addis et al. (2015) . The

authors address the operating room planning problem, and the

nurse-to-patient assignment problem in home care services using

the proposed cardinality-constrained uncertainty.

Similar to two-stage stochastic programs ( Birge & Louveaux,

2011 ), two-stage (adaptive) robust optimization addresses cases

when decisions can be split into two different sets. First, there

are the here-and-now decisions that have to be made prior to the

realization of the uncertainty. After the uncertainty is realized,

wait-and-see decisions are made. These are the recourse decisions

that are made to correct for the impact of the uncertainty. In

contrast to stochastic programming methods where the realization

of uncertainty is a product of a stochastic process (e.g., sample

from a distribution or simulation), the realization of uncertainty in

the RO methodology is a product of an optimization model.

Ben-Tal, Goryashko, Guslitzer, and Nemirovski (2004) state that

in cases where recourse actions are available, two-stage robust

optimization problems produce better solutions than the static

version. They show most cases of two-stage RO problems are

NP-hard and propose to restrict recourse solutions to be aﬃne

functions of uncertain data and then show cases where this

restriction produces tractable optimization problems. They apply

the proposed approximation to an inventory problem and solve

the resulting reformulation as a linear program. Later in Atamtürk

and Zhang (2007) a two-stage robust optimization approach for a

network design problem where demand is uncertain is proposed.

Theoretical complexity results and special cases are also presented.

The methodology is applied to various problems such as lot-sizing

and location-transportation. Thiele, Terry, and Epelman (2009) pro-

pose a general framework for two-stage robust LP problems. To

solve these problems, an algorithm based on Kelley’s cutting-plane

algorithm ( Kelley, 1960 ) is proposed. Gabrel, Lacroix, Murat, and

Remli (2014a) formulate the location-transportation problem with

demand uncertainty using a two-stage robust formulation. A

cutting-plane algorithm is used to obtain solutions. Zeng and

Zhao (2013) propose a column-and-constraint generation method

to solve two-stage robust problems and show that the solution

methodology performs better than the cutting-plane methods

proposed by Gabrel et al. (2014a) and Thiele et al. (2009) when

applied to location-transportation problems. In addition, they

provide theoretical results that show their proposed algorithm has

a superior worst-case complexity as compared with one proposed

by Thiele et al. (2009) . For more information regarding adaptability

in robust optimization and its approximations, readers are referred

to Bertsimas et al. (2011) and references there in.

There is not much literature on two-stage robust optimization

problems with mixed-integer recourse structure. Zhao and Zeng

(2012) propose a formulation, conditions, and a solution method

based on their column-and-constraint generation method ( Zeng &

Zhao, 2013 ) to obtain provably optimal solutions to this class of

problems. Approximation methods based on ﬁnite adaptability for

two-stage and multi-stage RO problems are proposed in Bertsimas

and Caramanis (2010) (see also Bertsimas et al., 2011 and refer-

ences therein). Although the recourse decisions in the SICU are

in the form of number of patients and restricted to be integer,

thanks to our novel formulation the integrality constraints can be

relaxed.

In our study, we base our theory on the work of Bertsimas

and Sim (2004) , Thiele et al. (2009) , Gabrel et al. (2014a) , and

Zeng and Zhao (2013) . We propose a novel two-stage robust

formulation to model surgery planning with downstream resource

capacity. Both surgery durations and LOS in the SICU are uncertain

parameters. Our formulation naturally decomposes the problem

into sub-problems for ORs and downstream units. We propose a

column-and-constraint generation algorithm to solve this problem.

The formulation can be used in other important applications such

as project management, manufacturing, etc., where downstream

resources are shared by multiple entities.

3. Model development

In this section, the model development for planning of surgery

and downstream capacity under uncertainty is presented. First,

some notation and a deterministic formulation is presented.

Next, we deﬁne our model of uncertainty in detail. Finally, the

robust formulation to model this problem is presented. We go in

depth to study the structure of the proposed formulation and its

characteristics in the subsequent section.

3.1. Deﬁnitions and deterministic formulation

We deﬁne set B as the set of surgery blocks in a given decision

period (usually a week or two weeks long). Set S deﬁnes the set of

specialties that are included in the cyclic schedule. Each block, b

∈ B , is dedicated to only one type of specialty while there can be

multiple blocks of the same specialty during a cycle in the surgery

schedule. B

is used to denote the set of blocks for specialty

s during the planning horizon. Set I = { 1 , . . . , n } represents the

elective surgery patients. Set I

⊆ I represents the set of patients

that require specialty s . Note that each patient is assigned to one

specialty. Therefore patient i of specialty s can be assigned to any

of the blocks b ∈ B

during the planning horizon. We assume,

without loss of generality, that the length of the planning horizon

is T days and is an integer multiple of the surgery schedule cycle

length. Each surgery block b has a pre-allocated length of time

which is denoted by h

on a speciﬁc day t

. Due to uncertainty

in surgery times, a surgery block may need to use extra time

to ﬁnish the scheduled surgeries. Therefore overtime cost c

for

each unit of time is incurred for specialty s . For ease of modeling,

a dummy block b



∈ B , is considered for patients who are not

assigned to any surgery blocks during the planning horizon T and

are postponed be assigned to surgery during the next planning

horizon. The cost of assigning patient i to each block is deﬁned

as a

, where a

< a



∀ b  = b



. This represents the admission costs

for each patient considering their waiting times and priorities.

Associated with each patient i , there is the length-of-stay l

which denotes the number of consecutive days that the patient

is required to stay in the SICU. In addition, there is the surgery

duration d

, which represents the time required to perform the

surgery for patient i . The SICU has limited number of beds on each

day, represented by r

. In the case of lack of capacity in the SICU,

a patient will be denied admission to the SICU and/or has to be

transferred to units with lower level of care. The cost incurred for

each day a patient is not receiving the care in the SICU is denoted

by e

. Table 1 summarizes the list of sets and parameters used in

our model.

To formulate the problem, we deﬁne x

sib

be equal to one if

patient i with specialty s is assigned to perform surgery on block

b , and is set to zero otherwise. y

is one if patient i is in need of

a SICU bed on day t , and is zero otherwise. Continuous decision

variable o

captures the amount of overtime incurred during the

surgery in block b . u

counts the number of patients on day t that

剩余19页未读，继续阅读

xutingyu_01

粉丝: 0
资源: 2

两阶段鲁棒优化：解决择期手术及下游资源调度难题

Matlab代码纯原创，两阶段鲁棒优化调度文献+复现代码 复现《微电网两阶段鲁棒优化调度方法_刘一欣》

两阶段鲁棒优化以及列与约束生成算法(C&amp;CG)的matlab代码实现

电网两阶段鲁棒性优化ccg算法

微电网两阶段鲁棒优化调度

微电网两阶段鲁棒优化经济调度方法

两阶段鲁棒无功优化代码matlab

原创代码,完美复现,微电网两阶段鲁棒优化,基于matlab+yalmip+cplex实现

微电网两阶段鲁棒优化经济调度

两阶段鲁棒优化用matlab写

两阶段鲁棒matlab

最新资源

Matlab代码纯原创，两阶段鲁棒优化调度文献+复现代码复现《微电网两阶段鲁棒优化调度方法_刘一欣》

两阶段鲁棒优化以及列与约束生成算法(C&CG)的matlab代码实现