Building cyclic master surgery schedules with leveled resulting bed occupancy

This paper proposes and evaluates a number of models for building surgery schedules with leveled resulting bed occupancy. The developed models involve two types of constraints. Demand constraints ensure that each surgeon (or surgical group) obtains a specific number of operating room blocks. Capacity constraints limit the available blocks on each day. Furthermore, the number of operated patients per block and the length of stay of each operated patient are dependent on the type of surgery. Both are considered stochastic, following a multinomial distribution. We develop a number of mixed integer programming based heuristics and a metaheuristic to minimize the expected total bed shortage and present computational results.     

The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care

A general problem in health-care consists in allocating some scarce medical resource, such as operating rooms or medical staff, to medical specialties in order to keep the queue of patients as short as possible. A major difficulty stems from the fact that such an allocation must be established several months in advance, and the exact number of patients for each specialty is an uncertain parameter. Another problem arises for cyclic schedules, where the allocation is defined over a short period, e.g. a week, and then repeated during the time horizon. However, the demand typically varies from week to week: even if we know in advance the exact demand for each week, the weekly schedule cannot be adapted accordingly. We model both the uncertain and the cyclic allocation problem as adjustable robust scheduling problems. We develop a row and column generation algorithm to solve this problem and show that it corresponds to the implementor/adversary algorithm for robust optimization recently introduced by Bienstock for portfolio selection. We apply our general model to compute master surgery schedules for a real-life instance from a large hospital in Oslo.     

A pre-assignment heuristic algorithm for the Master Surgical Schedule Problem (MSSP)

In this paper a 0–1 linear programming model and a solution heuristic algorithm are developed in order to solve the so-called Master Surgical Schedule Problem (MSSP). Given a hospital department made up of different surgical units (i.e. wards) sharing a given number of Operating Rooms (ORs), the problem herein addressed is determining the assignment among wards and ORs during a given planning horizon, together with the subset of patients to be operated on during each day. Different resource constraints related to operating block time length, maximum OR overtime allowable by collective labour agreement and legislation, patient length of stay (LOS), available OR equipment, number of surgeons, number of stay and ICU beds, are considered. Firstly, a 0–1 linear programming model intended to minimise a cost function based upon a priority score, that takes into proper account both the waiting time and the urgency status of each patient, is developed. Successively, an heuristic algorithm that enables us to embody some pre-assignment rules to solve this NP-hard combinatorial optimisation problem, is presented. In particular, we force the assignment of each patient to a subset of days depending on his/her expected length of stay in order to allow closing some stay areas during the weekend and hence reducing overall hospitalisation cost of the department. The results of an extensive computational experimentation aimed at showing the algorithm efficiency in terms of computational time and solution effectiveness are given and analysed.     

Modelling activities at a neurological rehabilitation unit

A queuing model of a specialist neurological rehabilitation unit is studied. The application is to the Neurological Rehabilitation Centre at Rookwood Hospital (Cardiff, UK), the national rehabilitation unit for Wales. Due to high demand this 21-bed inpatient facility is nearly always at maximum occupancy, and with a significant bed-cost per day this makes it a prime candidate for mathematical modelling. Central to this study is the concept that treatment intensity has an effect on patient length of stay. The model is constructed in four stages. First, appropriate patient groups are determined based on a number of patient-related attributes. Second, a purpose-built scheduling program is used to deduce typical levels of treatment to patients of each group. These are then used to estimate the mean length of stay for each patient group. Finally, the queuing model is constructed. This consists of a number of disconnected homogeneous server queuing systems; one for each patient group. A Coxian phase-type distribution is fitted to the length of time from admission until discharge readiness and an exponential distribution models the remainder of time until discharge. Some hypothetical scenarios suggested by senior management are then considered and compared on the grounds of a number of performance measures and cost implications.     

The optimal allocation of server time slots over different classes of patients

We present a model for assigning server time slots to different classes of patients. The objective is to minimize the total expected weighted waiting time of a patient (where different patient classes may be assigned different weights). A bulk service queueing model is used to obtain the expected waiting time of a patient of a particular class, given a feasible allocation of service time slots. Using the output of the bulk service queueing models as the input of an optimization procedure, the optimal allocation scheme may be identified. For problems with a large number of patient classes and/or a large number of feasible allocation schemes, a step-wise heuristic is developed. A common example of such a system is the allocation of operating room time slots over different medical disciplines in a hospital.     

Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition

This paper presents a stochastic optimization model and efficient decomposition algorithm for multi-site capacity planning under the uncertainty of the TFT-LCD industry. The objective of the stochastic capacity planning is to determine a robust capacity allocation and expansion policy hedged against demand uncertainties because the demand forecasts faced by TFT-LCD manufacturers are usually inaccurate and vary rapidly over time. A two-stage scenario-based stochastic mixed integer programming model that extends the deterministic multi-site capacity planning model proposed by Chen et al. (2010) [1] is developed to discuss the multi-site capacity planning problem in the face of uncertain demands. In addition a three-step methodology is proposed to generate discrete demand scenarios within the stochastic optimization model by approximating the stochastic continuous demand process fitted from the historical data. An expected shadow-price based decomposition, a novel algorithm for the stage decomposition approach, is developed to obtain a near-optimal solution efficiently through iterative procedures and parallel computing. Preliminary computational study shows that the proposed decomposition algorithm successfully addresses the large-scale stochastic capacity planning model in terms of solution quality and computation time. The proposed algorithm also outperforms the plain use of the CPLEX MIP solver as the problem size becomes larger and the number of demand scenarios increases.     

Determination of number of dedicated OR's and supporting pricing mechanisms for emergent surgeries

Inefficient management of emergent surgeries in hospitals can, in part, be attributed to a lack of rigorous analysis appropriate to capturing the underlying uncertainties inherent to this process and a pricing mechanism to ensure its financial viability. We develop a non-preemptive multi-priority queueing model that optimally manages emergent surgeries and supports the resource allocation decision-making process. Specifically, we utilize queueing and discrete event simulation to develop empirical models for determining the required number of emergent operating rooms for a hospital surgical department. We also present algorithms that estimate the appropriate pricing for patient surgeries differentiated by priority level given the patient demand and the resources reserved to meet this demand.     

Modelling the size and skill-mix of hospital nursing teams

Previously published work has described the development of a hospital capacity simulation tool, PROMPT. PROMPT has now been adopted by a number of hospitals in the UK and is used for both strategic and operational planning and management of key hospital resources. The work, as presented here, extends the PROMPT functionality to consider in more detail workforce issues. In particular, working with some of the current hospital users, the research has focussed on detailed planning for calculating the size and skill-mix of inpatient nursing teams. The chosen methodology utilizes both simulation and optimization. Outputs from the PROMPT three-phase discrete event simulation are fed into a stochastic programme which suggests the optimal number of nurses to employ (whole time equivalents) by skill-mix and the corresponding numbers by shift. A novel feature of the tool is the ability to predict and compare nursing needs based on different methods of capturing patient-to-nurse ratios as currently adopted across the UK National Health Service. Illustrative results from one hospital demonstrate that although the overall sizes of nursing teams on different wards are of an acceptable level and comparable to the outputs from the simulation phase of the work, often the number of nurses employed at different grades is not well matched to patient needs and the skill-mix should be reconsidered. Results from the optimization phase of the work suggest that it is cost beneficial to increase the number of permanently employed nurses to account for fluctuations in demand and corresponding high costs of temporary (agency) nurses. The scenario functionality of the tool permits for the study of changing size and skill-mix as a consequence of changes in patient volumes, patient case-mix, numbers of beds and length of stay.     

Simulation optimization for an emergency department healthcare unit in Kuwait

This paper integrates simulation with optimization to design a decision support tool for the operation of an emergency department unit at a governmental hospital in Kuwait. The hospital provides a set of services for different categories of patients. We present a methodology that uses system simulation combined with optimization to determine the optimal number of doctors, lab technicians and nurses required to maximize patient throughput and to reduce patient time in the system subject to budget restrictions. The major objective of this decision supporting tool is to evaluate the impact of various staffing levels on service efficiency. Experimental results show that by using current hospital resources, the optimization simulation model generates optimal staffing allocation that would allow 28% increase in patient throughput and an average of 40% reduction in patients’ waiting time.     

Modeling formulation and a new heuristic for the railroad blocking problem

The railroad blocking problem is an important issue at the tactical level of railroad freight transportation. This problem consists of determining paths between the origins and destinations of each shipment to minimize the operating and user costs while satisfying the railroad supply and demand restrictions. A mixed-integer program (MIP) is developed to find the optimal paths, and a new heuristic is developed to solve the proposed model. This heuristic decomposes the model into two sub-problems of manageable size and then provides feasible solutions. We discuss the performance of the proposed heuristic for a set of instances with up to 90 stations. A comparison with the CPLEX MIP solver shows that the heuristic gives the exact solution for 10 out of 15 instances. For the remaining instances, the heuristic obtained solutions within a tolerance of 0.03–0.84%. Furthermore, compared with the CPLEX MIP solver, the heuristic reduced the run time by an average of 85% for all 15 instances. Finally, we present the computational results of the heuristic applied to Iranian railroads.     

Simulating hospital emergency departments queuing systems: (GI/G/m(t)) : (IHFF/N/∞)

The queuing system to be considered in this paper is a real case study with the following characteristics: (1) general independent interarrival distribution, (2) general service-time distribution, (3) limited waiting room, (4) patient's priorities increase up to a certain number, (5) time-dependent number of servers (doctors), (6) infinite patient population, (7) each server meets the system only once within a certain period of time, while the total number of the available servers is known. The system to be considered is a hospital's Emergency Department and a general simulation algorithm is presented as well as the system's operating characteristics. This algorithm, implemented on a mini-computer or an inexpensive microcomputer solved a sophisticated operations research problem.     

基于二项logit模型的房型选择行为分析

目前,学者多利用集计模型分析、预测酒店顾客群体的客房需求,忽略了个体间的差异.针对不同房型分别建立非集计的二项logit模型,分析顾客的不同属性:性别、住宿天数、入住时间、退房时间和月份对其房型的选择行为的影响,并预测不同房型的预定概率.结果表明:商务/行政大床房、商务/行政双床房、商务/行政三人套房在不同因素的影响下,其预定概率存在显著差异.为酒店合理应对波动较大的顾客需求提供了理论基础.     

Optimum service capacity and demand management with price incentives

Service firms periodically face fluctuating demand levels. They incur high costs to handle peak demand and pay for under-utilized capacity during low demand periods. In this paper, we develop a mixed integer programming (MIP) model based on the real life experience of a Brazilian telecommunications firm. The model determines the optimum staffing requirements with different seniority levels for employees, as well as the distribution and balancing of workload utilizing flexibility of some customers in their service completion day. The proposed MIP uses monetary incentives to smooth the workload by redistributing some of the peak demand, thereby increasing capacity utilization. Due to the intractable nature of optimizing the proposed MIP model, we present a heuristic solution approach. The MIP model is applied to the case of the examined Brazilian Telecommunications firm. The computational work on this base case and its extensions shows that the proposed MIP model is of merit, leading to approximately seventeen percent reduction in the base case operating costs. Extensive computational work demonstrates that our heuristic provides quality solutions in very short computational times. The model can also be used to select new customers based on the workload, the revenue potential of these new customers and their flexibility in accepting alternate service completion dates. The generic structure of the proposed approach allows for its application to a wide variety of service organizations facing similar capacity and demand management challenges. Such wide applicability enhances the value of our work and its expected benefits.     

A stochastic model for operating room planning with elective and emergency demand for surgery

This paper describes a stochastic model for Operating Room (OR) planning with two types of demand for surgery: elective surgery and emergency surgery. Elective cases can be planned ahead and have a patient-related cost depending on the surgery date. Emergency cases arrive randomly and have to be performed on the day of arrival. The planning problem consists in assigning elective cases to different periods over a planning horizon in order to minimize the sum of elective patient related costs and overtime costs of operating rooms. A new stochastic mathematical programming model is first proposed. We then propose a Monte Carlo optimization method combining Monte Carlo simulation and Mixed Integer Programming. The solution of this method is proved to converge to a real optimum as the computation budget increases. Numerical results show that important gains can be realized by using a stochastic OR planning model.     

A Dynamic Supplier Selection and Inventory Management Model for a Serial Supply Chain with a Novel Supplier Price Break Scheme and Flexible Time Periods

A new supplier price break and discount scheme taking into account order frequency and lead time is introduced and incorporated into an integrated inventory planning model for a serial supply chain that minimizes the overall incurred cost including procurement, inventory holding, production, and transportation. A mixed-integer linear programming (MILP) formulation is presented addressing this multi-period, multi-supplier, and multi-stage problem with predetermined time-varying demand for the case of a single product. Then, the length of the time period is considered as a variable. A new MILP formulation is derived when each period of the model is split into multiple sub-periods, and under certain conditions, it is proved that the optimal solution and objective value of the original model form a feasible solution and an upper bound for the derived model. In a numerical example, three scenarios of the derived model are solved where the number of sub-period is set to 2, 3, and 4. The results further show the decrease of the optimal objective value as the length of the time period is shortened. Sufficient evidence demonstrates that the length of the time period has a significant influence on supplier selection, lot sizing allocation, and inventory planning decisions. This poses the necessity of the selection of appropriate length of a time period, considering the trade-off between model complexity and cost savings.     

Patient mix optimization in tactical cardiothoracic surgery planning: a case study

Cardiothoracic surgery planning involves different resourcessuch as operating theatre (OT) time, medium care beds, intensivecare beds and nursing staff. Within cardiothoracic surgery differentcategories of patients can be distinguished with respect totheir requirements of resources. The mix of patients is, therefore,an important aspect of decision making for the hospital to managethe use of these resources. A master OT schedule is used atthe tactical level of planning for deriving the weekly OT plan.It defines for each day of a week the number of OT hours availableand the number of patients operated from each patient category.We develop a model for this tactical level planning problem,the core of which is a mixed integer linear program. The modelis used to evaluate scenarios for surgery planning at tacticalas well as strategic levels, demonstrating the potential ofinteger programming for providing recommendations for change.     

Master surgery scheduling with consideration of multiple downstream units

We consider a master surgery scheduling (MSS) problem in which block operating room (OR) time is assigned to different surgical specialties. While many MSS approaches in the literature consider only the impact of the MSS on operating theater and operating staff, we enlarge the scope to downstream resources, such as the intensive care unit (ICU) and the general wards required by the patients once they leave the OR. We first propose a stochastic analytical approach, which calculates for a given MSS the exact demand distribution for the downstream resources. We then discuss measures to define downstream costs resulting from the MSS and propose exact and heuristic algorithms to minimize these costs.     

Robust berth scheduling with uncertain vessel delay and handling time

In container terminals, the actual arrival time and handling time of a vessel often deviate from the scheduled ones. Being the input to yard space allocation and crane planning, berth allocation is one of the most important activities in container terminals. Any change of berth plan may lead to significant changes of other operations, deteriorating the reliability and efficiency of terminal operations. In this paper, we study a robust berth allocation problem (RBAP) which explicitly considers the uncertainty of vessel arrival delay and handling time. Time buffers are inserted between the vessels occupying the same berthing location to give room for uncertain delays. Using total departure delay of vessels as the service measure and the length of buffer time as the robustness measure, we formulate RBAP to balance the service level and plan robustness. Based on the properties of the optimal solution, we develop a robust berth scheduling algorithm (RBSA) that integrates simulated annealing and branch-and-bound algorithm. To evaluate our model and algorithm design, we conduct computational study to show the effectiveness of the proposed RBSA algorithm, and use simulation to validate the robustness and service level of the RBAP formulation.     

多目的地多停车场系统动态停车分配模型

在一个多目的地多停车场系统中,每个目的地附近有多个停车场可供选择,每个停车场也可供多个目的地的停车需求停车。每个目的地的停车需求在各停车场的停车量即为停车分配问题. 本文定义了停车量分配均衡原则:各目的地的驾驶员总是首选最低费用(包括在停车场内的停车费用以及停车时间、步行时间转换后的货币成本,其中停车费用及在停车场内的车位找寻时间都正相关于该停车场当前时刻停车饱和度)的停车场停车;由于停车场具有容量限制,当费用最低的停车场已满则再选择费用次低的停车场,以此类推;所有没被使用的停车场或者比被使用的停车场具有更高的费用或者停车位已满。考虑停车需求和各停车场内空余泊位数的实时动态特性,提出了与该均衡原则等价的数学规划模型,证明了其解的唯一性并设计了求解算法。通过两个算例对模型进行了验证,并再现了目的地附近各停车场内车位占用变化规律,从而为动态停车收费、停车选址规划等提供依据。     

Production planning via scenario modelling

Several Linear Programming (LP) and Mixed Integer Programming (MIP) models for the production and capacity planning problems with uncertainty in demand are proposed. In contrast to traditional mathematical programming approaches, we use scenarios to characterize the uncertainty in demand. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield a nonanticipative or implementable policy. Such an approach makes it possible to model nonstationarity in demand as well as a variety of recourse decision types. Two scenario-based models for formalizing implementable policies are presented. The first model is a LP model for multi-product, multi-period, single-level production planning to determine the production volume and product inventory for each period, such that the expected cost of holding inventory and lost demand is minimized. The second model is a MIP model for multi-product, multi-period, single-level production planning to help in sourcing decisions for raw materials supply. Although these formulations lead to very large scale mathematical programming problems, our computational experience with LP models for real-life instances is very encouraging.