Dynamic multi-priority,multi-class patient scheduling with stochastic service times

Efficient patient scheduling has significant operational, clinical and economical benefits on health care systems by not only increasing the timely access of patients to care but also reducing costs. However, patient scheduling is complex due to, among other aspects, the existence of multiple priority levels, the presence of multiple service requirements, and its stochastic nature. Patient appointment (allocation) scheduling refers to the assignment of specific appointment start times to a set of patients scheduled for a particular day while advance patient scheduling refers to the assignment of future appointment days to patients. These two problems have generally been addressed separately despite each being highly dependent on the form of the other. This paper develops a framework that incorporates stochastic service times into the advance scheduling problem as a first step towards bridging these two problems. In this way, we not only take into account the waiting time until the day of service but also the idle time/overtime of medical resources on the day of service. We first extend the current literature by providing theoretical and numerical results for the case with multi-class, multi-priority patients and deterministic service times. We then adapt the model to incorporate stochastic service times and perform a comprehensive numerical analysis on a number of scenarios, including a practical application. Results suggest that the advance scheduling policies based on deterministic service times cannot be easily improved upon by incorporating stochastic service times, a finding that has important implications for practice and future research on the combined problem.     

随机服务时间下异质患者门诊预约调度优化

考虑随机服务时间与行为特征互不相同的异质患者,建立随机混合整数规划模型对门诊预约调度问题展开研究。首先在给定服务顺序的假设下求解了两个患者的预约调度问题;在此基础上,设计启发式算法对多个患者预约方案和服务顺序同时进行优化。数值结果表明:当患者服务时间为独立同分布的随机变量时,患者预约时间间隔呈现先增加后减少的圆顶形状;当患者服务时间服从不同分布时,通过与样本平均近似方法对比,验证了启发式算法的计算效率和有效性。     

Capacity allocation for demand of different customer-product-combinations with cancellations, no-shows, and overbooking when there is a sequential delivery of service

We consider a problem where different classes of customers can book different types of services in advance and the service company has to respond immediately to the booking request confirming or rejecting it. Due to the possibility of cancellations before the day of service, or no-shows at the day of service, overbooking the given capacity is a viable decision. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as the cost of overtime. For the calculation of the latter, information of the underlying appointment schedule is required. Throughout the paper we will relate the problem to capacity allocation in radiology services. Drawing upon ideas from revenue management, overbooking, and appointment scheduling we model the problem as a Markov decision process in discrete time which due to proper aggregation can be optimally solved with an iterative stochastic dynamic programming approach. In an experimental study we successfully apply the approach to a real world problem with data from the radiology department of a hospital. Furthermore, we compare the optimal policy to four heuristic policies, of whom one is currently in use. We can show that the optimal policy significantly improves the currently used policy and that a nested booking limit type policy closely approximates the optimal policy and is thus recommended for use in practice.     

Computationally efficient evaluation of appointment schedules in health care

We consider the problem of evaluating and constructing appointment schedules for patients in a health care facility where a single physician treats patients in a consecutive manner, as is common for general practitioners, clinics and for outpatients in hospitals. Specifically, given a fixed-length session during which a physician sees K patients, each patient has to be given an appointment time during this session in advance. Optimising a schedule with respect to patient waiting times, physician idle times, session overtime, etc. usually requires a heuristic search method involving a huge number of repeated schedule evaluations. Hence, our aim is to obtain accurate predictions at very low computational cost. This is achieved by (1) using Lindley’s recursion to allow for explicit expressions and (2) choosing a discrete-time (slotted) setting to make those expressions easy to compute. We assume general, possibly distinct, distributions for the patients’ consultation times, which allows to account for multiple treatment types, emergencies and patient no-shows. The moments of waiting and idle times are obtained and the computational complexity of the algorithm is discussed. Additionally, we calculate the schedule’s performance in between appointments in order to assist a sequential scheduling strategy.     

Minimizing Labor Requirements in a Periodic Vehicle Loading Problem

In this paper, we address a logistics problem that a manufacturer of auto parts in the north of Spain described to the authors. The manufacturer stores products in its warehouse until customers retrieve them. The customers and the manufacturer agree upon an order pickup frequency. The problem is to find the best pickup schedule, which consists of the days and times during the day that each customer is expected to retrieve his/her order. For a given planning horizon, the optimization problem is to minimize the labor requirements to load the vehicles that the customers use to pick up their orders. Heuristically, we approach this situation as a decision problem in two levels. At the first level, customers are assigned to a calendar, consisting of a set of days with the required frequency during the planning horizon. Then, for each day, the decision at the second level is to assign each customer to a time slot. The busiest time slot determines the labor requirement for a given day. Therefore, once customers have been assigned to particular days in the planning horizon, the second-level decision is a multiprocessor scheduling problem, where each time slot is the equivalent of a processor, and where the objective is to minimize the makespan. A metaheuristic procedure is developed for the problem of minimizing labor requirements in this periodic vehicle-loading problem and artificial as well as real data are used to assess its performance.     

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.     

Approximate dynamic programming for capacity allocation in the service industry

We consider a problem where different classes of customers can book different types of service in advance and the service company has to respond immediately to the booking request confirming or rejecting it. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as cost of overtime. For the calculation of the latter, information on the underlying appointment schedule is required. In contrast to most models in the literature we assume that the service time of clients is stochastic and that clients might be unpunctual. Throughout the paper we will relate the problem to capacity allocation in radiology services. The problem is modeled as a continuous-time Markov decision process and solved using simulation-based approximate dynamic programming (ADP) combined with a discrete event simulation of the service period. We employ an adapted heuristic ADP algorithm from the literature and investigate on the benefits of applying ADP to this type of problem. First, we study a simplified problem with deterministic service times and punctual arrival of clients and compare the solution from the ADP algorithm to the optimal solution. We find that the heuristic ADP algorithm performs very well in terms of objective function value, solution time, and memory requirements. Second, we study the problem with stochastic service times and unpunctuality. It is then shown that the resulting policy constitutes a large improvement over an “optimal” policy that is deduced using restrictive, simplifying assumptions.     

Optimized appointment scheduling

In service systems, in order to balance the server’s idle times and the customers’ waiting times, one may fix the arrival times of the customers beforehand in an appointment schedule. We propose a procedure for determining appointment schedules in such a D/G/1-type of system by sequentially minimizing the per-customer expected loss. Our approach provides schedules for any convex loss function; for the practically relevant cases of the quadratic and absolute value loss functions appealing closed-form results are derived. Importantly, our approach does not impose any conditions on the service time distribution; it is even allowed that the customers’ service times have different distributions.     

Sequential clinical scheduling with service criteria

This study investigates sequential appointment scheduling with service criteria. It uses a constraint-based approach with service criteria bounded in a constraint set in contrast to the more typical weighted linear objective function. Properties are derived and a sequential scheduling algorithm is developed. Fairness properties of generated schedules are considered in detail, where fairness is the uniformity of performance across patients. New unfairness measures are proposed and used to capture the inequity among patients assigned to different slots. Other criteria such as expectation and variance of patient waiting time, queue length, and overtime are also considered. The fairness/revenue tradeoff is investigated as is the flexibility of the constraint-based approach in handling unavailable time periods.     

Benefits of a truck appointment system on the service quality of inland transport modes at a multimodal container terminal

Container terminals pay more and more attention to the service quality of inland transport modes such as tucks, trains and barges. Truck appointment systems are a common approach to reduce truck turnaround times. This paper provides a tool to use the truck appointment system to increase not only the service quality of trucks, but also of trains, barges and vessels. We propose a mixed integer linear programming model to determine the number of appointments to offer with regard to the overall workload and the available handling capacity. The model is based on a network flow representation of the terminal and aims to minimize overall delays at the terminal. It simultaneously determines the number of truck appointments to offer and allocates straddle carriers to different transport modes. Numerical experiments, conducted on actual data, quantify the benefits of this combined solution approach. Discrete-event simulation validates the results obtained by the optimization model in a stochastic environment.     

Developing a platform for comparison of hospital admission systems: An illustration

There is an increasing need to develop a platform for comparing hospital admission planning systems due to a shift in the service paradigm in the health sector. The current service concept of hospital admission planning aims at optimising the use of scarce hospital resources without paying much attention to the level of service offered to patients. As patients nowadays do not accept long waiting times for hospital admission, it becomes necessary to consider alternative admission service concepts. Waiting lists have also become a political issue, and alternative concepts have been advocated such as giving all patients an appointment for admission. A simulation model was built to examine the impacts of extreme admission service concepts in a simplified hospital setting. The alternative concepts considered are based on the ‘zero waiting time’ principle (immediate treatment), and the ‘booked admissions’ principle (using an appointment for admission). The results of these admission service concepts are compared with the results of the current concept, based on the ‘maximising resource use’ principle. The paper deals with the development of a framework and tool that allows evaluating different, somehow conflicting, hospital admission planning concepts and the usefulness of such framework and tool for more refined/real-life approaches to hospital admission planning.     

Cover-Free Families and Topology-Transparent Scheduling for MANETs

We examine the combinatorial requirements of topology-transparent transmission schedules in a mobile ad hoc network (MANET). Specifically, if each of the N nodes has at most D active neighbors, we require the schedule to guarantee a collision-free transmission to each neighbor. This requirement is met by a cover-free family. We show that existing constructions for topology-transparent schedules correspond to an orthogonal array. Moreover, we show that Steiner systems support the largest number of nodes for a given schedule length. Both of these combinatorial objects are special cases of cover-free families. Analytically and numerically, we examine slot guarantees, expected throughput, and normalized expected throughput for systems of small strength, exploring the sensitivity of the response to D. Expected throughput provides a better performance metric than the minimum throughput results obtained earlier. The impact of a more realistic model of acknowledgments is also examined. The extension of the schedule to multiple frames returns us to the orthogonal arrays. The very density of Steiner systems that afforded an improvement over orthogonal arrays in one frame impedes the best extension to more frames.     

New differentiated consensus problem with topology cost constraints

A new differentiated consensus problem is studied. The problem is, given a system with multiple classes, consensus is targeted for each class and the consensus values can be different among the classes. Specifically, differentiated consensus is studied in a distributed stochastic network of nodes (or agents), where tasks assigned with different priorities are serviced. The network is assumed to have a switching topology and involves noises, delays in measurements, and topology cost constraints. The goal is to reach a balanced load (i.e., consensus) across the network and, at the same time, to satisfy the topology cost constraint, both for each priority class. A new control protocol is proposed, with which the network resources are allocated in a randomized way with a probability assigned to each priority class. It is shown that the control protocol meets the topology cost constraint and can be used to reach an approximate consensus for each of the priority classes in the network.     

Block appointment systems for outpatient clinics with multiple doctors

Studies of appointment systems have to some extent led to a wide acceptance of individual or block appointment schemes in private practice and outpatient clinics. Most of the studies assume there is one punctual doctor in a clinic, which is often not the case in reality. Motivated by observations of actual clinic operations, we develop a block appointment system for clinic operations with multiple random arriving doctors. Through extensive simulation studies, we identify properties shared by the best appointment schedules. With these properties we can design a scheme based on simulation search that provides the optimal schedule for a given scheduling environment in an acceptable computation time. A simple (suboptimal) appointment rule is also proposed.     

Multi-parallel work centers scheduling optimization with shared or dedicated resources in low-volume low-variety production systems

A new methodology for modeling large-scale scheduling problems in low-volume low-variety production systems is proposed through this paper. Such scheduling problems are constrained by limited time and resources, where each work center is assigned a unique statement of work, to be completed on-time with the budgeted number of resources. Products assembled in low-volume low-variety production systems are processed through a series of stations referred to as work centers, where varying levels and classifications of resources are deployed onto the product. Aircraft, heavy aero-structures, and heavy military equipment are examples of products assembled in low-volume low-variety production systems. To ensure products are delivered on-time and on-budget, it is crucial to execute to a detailed schedule, such that all precedence, resource, zonal, and other constraints and characteristics inherent in such production systems are successfully satisfied. Despite the criticality of detailed schedules in delivering products on-time and on-budget, limited research is reported on mixed-integer programming approaches for scheduling optimization of activities in low-volume low-variety production systems. The discrete-time linear mixed-integer mathematical programming model developed in this paper fills the gap in the current literature with a direct impact on the organizations’ service levels and bottom line. The proposed mathematical programming models are validated through a real-world case-study of the assembly process of a narrow body aircraft to ensure compatibility in the modeling of large-scale industrial problems.     

A discrete-time retrial queueing model with one server

This paper presents a one-server queueing model with retrials in discrete-time. The number of primary jobs arriving in a time slot follows a general probability distribution and the different numbers of primary arrivals in consecutive time slots are mutually independent. Each job requires from the server a generally distributed number of slots for its service, and the service times of the different jobs are independent. Jobs arriving in a slot can start their service only at the beginning of the next slot. When upon arrival jobs find the server busy all incoming jobs are sent into orbit. When upon arrival in a slot jobs find the server idle, then one of the incoming jobs (randomly chosen) in that slot starts its service at the beginning of the next slot, whereas the other incoming jobs in that slot, if any, are sent into orbit. During each slot jobs in the orbit try to re-enter the system individually, independent of each other, with a given retrial probability.     

基于满意度的预约门诊排队策略研究

为了推进预约挂号服务在医院有效的应用,本文结合实际情形,提出了病人满意度度量的新指标——加权病人等待时间,建立了以最大化病人满意度为目标的排队模型,并分析了医院目前常用的两种预约排队策略:不同优先级预约排队策略与时间段优先型预约排队策略。通过两种预约策略的比较,得到后者优于前者;通过预约与非预约策略的比较,得到预约策略优于非预约策略。在此基础上,对两种预约策略进行优化分析,求解出两种预约策略分别对应的最佳预约与非预约病人比例。最后,通过数值分析说明了应用预约策略对改善病人等待满意度的合理性及有效性,并对应用预约策略达到更好的满意度提出了可行建议。     

Proactive heuristic procedures for robust project scheduling: An experimental analysis

Solution-robust project scheduling is a growing research field aiming at constructing proactive schedules to cope with multiple disruptions during project execution. When stochastic activity durations are considered, including time buffers between activities is a proven method to improve the stability of a baseline schedule.     

Improving appointment scheduling for medical screening

We investigate the optimization of appointment scheduling forbreast cancer screening, using the fact that a woman's attendanceprobability can be predicted. The methodology used applies tomedical screening in general. The results of the mathematical investigation presented in thispaper include a new formula for the cost of a screening session,a probabilistic model of rebooking appointments, a model ofattendance probability as a function of previous performance,and a heuristic cost optimization procedure. Breast Test Wales have improved efficiency by introducing heavilyoverbooked sessions for patients who are unlikely to attend.We use simulation modelling and insights from probability theoryto confirm the gain achieved by the Wales procedure and to assessthe further gain achievable by optimization of appointment scheduling.It is found that a gain in throughput of at least 10% can beobtained by optimizing appointment scheduling for screeningsessions, in particular by inviting patients in decreasing orderof attendance probability, and by overbooking near the end ofthe session. This avoids the need to set up dedicated sessionsfor poor attenders. Another possibility is to book patientswho change their appointment time, and who are therefore verylikely to attend, into dedicated sessions. The provision of appointment scheduling software with a built-insimulation and optimization module along the lines describedin this paper could enable radiographers to tailor appointmentscheduling for each area and so to schedule appointments veryefficiently.     

差异化需求下考虑患者预约行为的医疗服务供需匹配方法

如何根据患者的差异化需求,撮合医生与患者双方形成合理有效的医疗服务供需匹配,是医疗服务运作管理中重要的研究问题。本文针对医疗服务中医生与患者的实际需求,提出了一种考虑患者预约行为的匹配决策方法。在该方法中,首先依据患者的预约行为及特征分类;然后,通过计算不同情形下医患双方的差异度,获得了医患双方的满意度矩阵;在此基础上,提出了匹配预约患者与医生的E-HR算法,并进一步构建了匹配剩余患者和医生的多目标优化模型,通过模型求解得到最优匹配结果;最后,通过算例说明了本文提出方法的可行性和实用性。