Study On Stochastic Programming And Robust Optimization For Capacity Allocation And Scheduling Problems In Operating Rooms

With the improvement of living standards and health awareness, people have paid more and more attentions on the service quality of healthcare system. A surgery department is the core of a hospital, which is closely related to the health or even life of patients. Operating rooms are important technical departments and the places to rescue people's life, where the operating costs are almost the most expensive and the related human resources are the most extensive. Surgery processes are complicated and unpredicted. Thus, operating room management is an important issue troubled hospital managers. The significance of the paper is to find an optimal allocation of limited medical resources in a surgery department, reduce the waiting time of surgery patients; in the mean time, reduce the occurrence of unreasonable phenomenon and provide an effective scheduling to hospitals.The background of the work is AAA hospitals in China. We have investigated several public and private hospitals and found the key bottlenecks faced by hospital managers. The flow processes of surgeries and the related resource constraints have been described. The dissertation provides decision method of reducing waiting time of patients, improving efficiency of operating rooms simultaneously, and designing a patient-satisfied surgery schedule. The mixed integer programming, stochastic programming and robust optimization have been applied in the modeling processes. Exact and heuristic algorithms have been developed to solve operating room planning and scheduling problems.This dissertation focuses on the following five key aspects:(1) The problem of allocating limited operating room capacity among subspecialties in hospitals is focused. Since such an allocation is usually decided several weeks or even months before, the only information about future demands is its range. We focus on finding a robust solution that absorbs disturbances on the surgery demand. An adjustable robust model is developed to solve this surgery capacity allocation problem with demand uncertainty. An implementor-adversary algorithm is applied to solve the robust optimization model. We present computational results comparing the proposed robust optimization approach with scenario-based stochastic optimization; the results show that the robust optimization method has the benefit of limiting the worst-case outcome of the surgery capacity allocation problem. Additionally, we examine the impact of conservativeness of the robust model on revenue loss of surgery department.(2) The problem of surgery scheduling under uncertain surgery duration is focused. We develop a robust optimization method to solve the surgery scheduling issue. The surgery service duration, which is influenced by many factors, such as individual physical condition, the surgeon skills and etc. is uncertain in advance. How to effectively scheduling surgeries is a challenge task for managers in hospital. We give intervals of surgery service durations for each patient, with regard to the surgery deadline for each patient; a two-stage adjustable robust counterpart surgery scheduling model is built. The optimization software CPLEX is applied to solve the model. Numerical experiments indicate that our robust optimization approach performs excellent on controlling the occurrence of worst-case results. Additionally, considering surgery deadline in our issue reduces the revenue of surgery department.(3) The problem of surgery scheduling under surgery cancellation risk is focused. Under the consideration of surgery cancellation, a stochastic model was developed to minimize the total expected operating cost. A sample average approximation method is applied to transfer the stochastic model into a deterministic one. Numerical results indicate that high surgery cancellation risk helps to reduce the operating costs of hospitals and improve the OR efficiency but results in patients'dissatisfaction, and vice versa. A column-generation-based heuristic (CGBH) algorithm is developed to solve the surgery scheduling problem. The experiment results show that the CGBH algorithm performed as well as the CPLEX in the solution quality for small-scale problems; in the meantime, the algorithm can obtain solutions within a 5% gap of the lower bound obtained by the linear problem for large-scale problems that cannot be solved by CPLEX.(4) The joint surgery soheduling and surgeon rostering problem with regard to patients' preferences is focused. The background is the surgery department in private hospitals, who aim at high-end customer market in China. A patient preference-driven policy that incorporates surgeon scheduling into the surgery scheduling process is proposed to satisfy patients'personalised preferences for surgeons and surgery dates. A stochastic programming model is formulated. A column-generation-based preference algorithm is developed to solve the issue. Numerical results indicate that the column generation-based preference algorithm can obtain solutions within a 2% gap of the lower bound obtained by the relaxed linear problem. A speed-up strategy is developed and the influence of patients' preferences is analyzed.(5) A two-stage operating room scheduling approach is developed with regard to the number of recovery beds limited. The overall surgery processes in laminar-flow operating theaters is described, which includes set-up, anesthesia, operation, clean-up and recovery processes. The overall surgery processes are totally considered in the research. A surgery planning model and a daily surgery sequencing model are built separately. A particle swarm optimization algorithm combined with two-stage no-wait heuristic rules is proposed. The results prove that our approach is effective.