Beyond Patient Classification: Using Individual Patient Characteristics in Appointment Scheduling

Scheduling patients involves a trade‐off between the productivity of the service provider and customer service. This study considers how outpatient medical facilities can improve their appointment scheduling by incorporating individual patient information in the scheduling process. Specifically, we obtain data on patient characteristics and examination durations from a health clinic, describe how that data can be used to predict patient examination durations in the clinic's appointment scheduling system, and evaluate the benefit of using individual patient characteristics over a conventional classification method. Computational results illustrate this method of patient scheduling reduces an overall cost function comprised of patient wait time, physician idle time, and over time by up to 24.2%, particularly when patients are sequenced with short duration patients being scheduled first. Several environmental characteristics are found to play critical roles in determining the magnitude of the benefit, including patient punctuality, no‐show probability, the clinic duration, the appointment rule used for scheduling, and the ratio of the physician's idle time cost to the patient wait cost. We also detail and evaluate a practical procedure for using heterogeneous scheduling under a fixed schedule.     

Panel Size and Overbooking Decisions for Appointment‐Based Services under Patient No‐Shows

Many service systems that work with appointments, particularly those in healthcare, suffer from high no‐show rates. While there are many reasons why patients become no‐shows, empirical studies found that the probability of a patient being a no‐show typically increases with the patient's appointment delay, i.e., the time between the call for the appointment and the appointment date. This paper investigates how demand and capacity control decisions should be made while taking this relationship into account. We use stylized single server queueing models to model the appointments scheduled for a provider, and consider two different problems. In the first problem, the service capacity is fixed and the decision variable is the panel size; in the second problem, both the panel size and the service capacity (i.e., overbooking level) are decision variables. The objective in both cases is to maximize some net reward function, which reduces to system throughput for the first problem. We give partial or complete characterizations for the optimal decisions, and use these characterizations to provide insights into how optimal decisions depend on patient's no‐show behavior in regards to their appointment delay. These insights especially provide guidance to service providers who are already engaged in or considering interventions such as sending reminders in order to decrease no‐show probabilities. We find that in addition to the magnitudes of patient show‐up probabilities, patients' sensitivity to incremental delays is an important determinant of how demand and capacity decisions should be adjusted in response to anticipated changes in patients' no‐show behavior.     

Scheduling Methods for Efficient Stamping Operations at an Automotive Company

We consider scheduling issues at Beyçelik, a Turkish automotive stamping company that uses presses to give shape to metal sheets in order to produce auto parts. The problem concerns the minimization of the total completion time of job orders (i.e., makespan) during a planning horizon. This problem may be classified as a combined generalized flowshop and flexible flowshop problem with special characteristics. We show that the Stamping Scheduling Problem is NP‐Hard. We develop an integer programming‐based method to build realistic and usable schedules. Our results show that the proposed method is able to find higher quality schedules (i.e., shorter makespan values) than both the company's current process and a model from the literature. However, the proposed method has a relatively long run time, which is not practical for the company in situations when a (new) schedule is needed quickly (e.g., when there is a machine breakdown or a rush order). To improve the solution time, we develop a second method that is inspired by decomposition. We show that the second method provides higher‐quality solutions—and in most cases optimal solutions—in a shorter time. We compare the performance of all three methods with the company's schedules. The second method finds a solution in minutes compared to Beyçelik's current process, which takes 28 hours. Further, the makespan values of the second method are about 6.1% shorter than the company's schedules. We estimate that the company can save over €187,000 annually by using the second method. We believe that the models and methods developed in this study can be used in similar companies and industries.     

Scheduling Truck Arrivals at an Air Cargo Terminal

We consider the scheduling of truck arrivals at an air cargo terminal. By coordinating arrivals of cargo delivery trucks with outbound flight departure schedules, some of the shipments can be transferred directly to the departing flights, while others will be stored at the terminal's storage facility and incur extra handling and storage costs. The objective is to obtain a feasible schedule so as to minimize the total cost of operations. We formulate the problem as a time‐indexed integer program and show that, even with limited number of unloading docks at the terminal, the problem is non‐trivial (NP‐hard in the strong sense). Our solution method includes an exact solution procedure to determine an optimal unloading sequence for the shipments carried by each truck, together with a Lagrangian relaxation‐based heuristic for assigning trucks to truck docks and determining truck arrival times. We conducted computational experiments to test the performance of our solution method. Computational results show that our method can generate near‐optimal solutions efficiently. Our simulation results indicate that the scheduling approach proposed in this paper has the potential to generate significant cost savings over a first‐come, first‐served approach currently used at the air cargo terminal that we observed.     

Reserving Capacity for Urgent Patients in Primary Care

This paper examines the effect of the common practice of reserving slots for urgent patients in a primary health care practice on two service quality measures: the average number of urgent patients that are not handled during normal hours (either handled as overtime, referred to other physicians, or referred to the emergency room) and the average queue of non‐urgent or routine patients. We formulate a stochastic model of appointment scheduling in a primary care practice. We conduct numerical experiments to optimize the performance of this system accounting for revenue and these two service quality measures as a function of the number of reserved slots for urgent patients. We compare traditional methods with the advanced‐access system advocated by some physicians, in which urgent slots are not reserved, and evaluate the conditions under which alternative appointment scheduling mechanisms are optimal. Finally, we demonstrate the importance of patient arrival dynamics to their relative performance finding that encouraging routine patients to call for same‐day appointments is a key ingredient for the success of advanced‐access.     

Optimal Choice for Appointment Scheduling Window under Patient No‐Show Behavior

Observing that patients with longer appointment delays tend to have higher no‐show rates, many providers place a limit on how far into the future that an appointment can be scheduled. This article studies how the choice of appointment scheduling window affects a provider's operational efficiency. We use a single server queue to model the registered appointments in a provider's work schedule, and the capacity of the queue serves as a proxy of the size of the appointment window. The provider chooses a common appointment window for all patients to maximize her long‐run average net reward, which depends on the rewards collected from patients served and the “penalty” paid for those who cannot be scheduled. Using a stylized M/M/1/K queueing model, we provide an analytical characterization for the optimal appointment queue capacity K, and study how it should be adjusted in response to changes in other model parameters. In particular, we find that simply increasing appointment window could be counterproductive when patients become more likely to show up. Patient sensitivity to incremental delays, rather than the magnitudes of no‐show probabilities, plays a more important role in determining the optimal appointment window. Via extensive numerical experiments, we confirm that our analytical results obtained under the M/M/1/K model continue to hold in more realistic settings. Our numerical study also reveals substantial efficiency gains resulted from adopting an optimal appointment scheduling window when the provider has no other operational levers available to deal with patient no‐shows. However, when the provider can adjust panel size and overbooking level, limiting the appointment window serves more as a substitute strategy, rather than a complement.     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

Supply Chain Scheduling: Distribution Systems

We study conflict and cooperation issues arising in a supply chain where a manufacturer makes products which are shipped to customers by a distributor. The manufacturer and the distributor each has an ideal schedule, determined by cost and capacity considerations. However, these two schedules are in general not well coordinated, which leads to poor overall performance. In this context, we study two practical problems. In both problems, the manufacturer focuses on minimizing unproductive time. The distributor minimizes customer cost measures in the first problem and minimizes inventory holding cost in the second problem. We first evaluate each party's conflict, which is the relative increase in cost that results from using the other party's optimal schedule. Since this conflict is often significant, we consider several practical scenarios about the level of cooperation between the manufacturer and the distributor. These scenarios define various scheduling problems for the manufacturer, the distributor, and the overall system. For each of these scheduling problems, we provide an algorithm. We demonstrate that the cost saving provided by cooperation between the decision makers is usually significant. Finally, we discuss the implications of our work for how manufacturers and distributors negotiate, coordinate, and implement their supply chain schedules in practice.     

Scheduling of Multi‐skilled Staff Across Multiple Locations

We address the problem of assigning airline customer service agents (CSAs) to tasks related to departing flights, such as selling tickets and collecting boarding cards, at an international terminal of a large airport. The airline specifies minimum and target levels of staff and required (or desired) types and levels of skills for each location in each time period. The assignment problem is complicated by staff heterogeneity, time required for moves between locations, and lunch and rest‐break requirements. We present a mixed‐integer formulation that considers both staffing shortages and skills mismatches and show that the problem is NP‐hard. We derive valid inequalities that tighten the bounds within a branch‐and‐cut procedure, enabling us to obtain near‐optimal solutions for problems of realistic size very quickly. We also present a generalization to simultaneously optimize shift starting times and task assignments, which can aid in longer term workforce planning. Finally, we utilize our procedure to obtain managerial insights regarding the benefits of flexibility derived from more highly skilled staff, allowing more frequent moves, and choices of shift starting times. We also demonstrate the benefits of our procedure vs. a heuristic that mimics what an experienced scheduler might choose.     

Sequencing and Scheduling Appointments with Potential Call‐In Patients

This paper studies appointment scheduling for a combination of routine patients who book well in advance and last‐minute patients who call for an appointment later that same day. We determine when these same‐day patients should be scheduled throughout the day, and how the prospect of their arrivals affects the appointment times of the routine patients. By formulating the problem as a stochastic linear program, we are able to incorporate random and heterogeneous service times and no‐show rates, ancillary physician tasks, and appointment delay costs for same‐day patients who prefer to see the doctor as early as possible. We find that the optimal patient sequence is quite sensitive to the no‐show probabilities and the expected number of same‐day patients. We also develop two simple heuristic solutions to this combinatorial sequencing problem.     

Analysis of the List Scheduling Algorithm for Precedence Constrained Parallel Tasks

Given P processors, and a set of precedence constrained parallel tasks with their processor requirements and execution times, the problem of scheduling precedence constrained parallel tasks on multiprocessors is to find a nonpreemptive schedule of the tasks on a multiprocessor with P processors, such that the schedule length is minimized. We show that for many heuristic choices of the initial priority list, the list scheduling algorithm has worst-case performance ratio P, which is unbounded as P gets large. However, it is also shown that when task sizes are bounded from above by a fraction of P, the list scheduling algorithm has finite worst-case performance ratio. In particular, we prove that if all tasks request for no more than qP processors, where 0 < q < 1, then the worst-case performance ratio of the list scheduling algorithm is no larger than

Combinatorial Optimization in Real-Time Scheduling: Theory and Algorithms

Real-time computer systems are essential for many applications, such as robot control, avionics, medical instrumentation, manufacturing, etc. The correctness of the system depends on the temporal correctness as well as the functional correctness of the task executions. In order to assure temporal correctness it is necessary that the resources be scheduled to meet the temporal requirements of applications. When we consider the problem of nonpreemptive scheduling of a set of tasks in a processor for which no feasible solution exists, some tasks may have to be rejected so that a schedule can be generated for the rest. In this paper, we consider the problem of generating an optimal schedule such that the number of rejected tasks is minimized, and then the finish time is minimized for the accepted tasks. We propose to use an analytic approach to solve this problem. We first discuss the super sequence based technique which was originally proposed for reducing the search space in testing the feasibility of a task set. Then we show by the Conformation theorem that the super sequence constructed from the task set also provides a valid and reduced search space for the optimization problem. While the complexity of our scheduling algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case.     

Appointment Overbooking in Health Care Clinics to Improve Patient Service and Clinic Performance

The problem of no‐shows (patients who do not arrive for scheduled appointments) is particularly significant for health care clinics, with reported no‐show rates varying widely from 3% to 80%. No‐shows reduce revenues and provider productivity, increase costs, and limit patient access by reducing effective clinic capacity. In this article, we construct a flexible appointment scheduling model to mitigate the detrimental effects of patient no‐shows, and develop a fast and effective solution procedure that constructs near‐optimal overbooked appointment schedules that balance the benefits of serving additional patients with the potential costs of patient waiting and clinic overtime. Computational results demonstrate the efficacy of our model and solution procedure, and connect our work to prior research in health care appointment scheduling.     

Bundling and Scheduling Service Packages with Customer Behavior: Model and Heuristic

Past researchers have found evidence that customers consider the sequence of event utility when evaluating past and future service experiences. Specifically, the evidence confirms that the placement of a peak event, the utility of the last event, and the slope of event utility over time all affect customer behavior and perception. We formulate an optimization problem with a focus on optimizing schedule sequence characteristics in order to maximize customer experiences. We discuss possible contexts in which this type of scheduling might be considered and, as an example, present a particularly complex model of a world‐renowned performing arts venue. We solve the problem with a simulated annealing algorithm and further discuss the complexity and opportunities associated with this type of scheduling effort.     

An Auction Mechanism for Pricing and Capacity Allocation with Multiple Products

We consider a pricing and short‐term capacity allocation problem in the presence of buyers with orders for bundles of products. The supplier's objective is to maximize her net profit, computed as the difference between the revenue generated through sales of products and the production and inventory holding costs. The objective of each buyer is similarly profit maximization, where a buyer's profit is computed as the difference between the time‐dependent utility of the product bundle he plans to buy, expressed in monetary terms, and the price of the bundle. We assume that bundles' utilities are buyers' private information and address the problem of allocating the facility's output. We directly consider the products that constitute the supplier's output as market goods. We study the case where the supplier follows an anonymous and linear pricing strategy, with extensions that include quantity discounts and time‐dependent product and delivery prices. In this setting, the winner determination problem integrates the capacity allocation and scheduling decisions. We propose an iterative auction mechanism with non‐decreasing prices to solve this complex problem, and present a computational analysis to investigate the efficiency of the proposed method under supplier's different pricing strategies. Our analysis shows that the problem with private information can be effectively solved with the proposed auction mechanism. Furthermore, the results indicate that the auction mechanism achieves more than 80% of the system's profit, and the supplier receives a higher percentage of profit especially when the ratio of demand to available capacity is high.     

中小呼叫中心月度排班优化模型与算法

国内中小呼叫中心制定坐席人员月度排班表时,通常考虑劳动法规合同约束和体现企业自身用工管理诉求。构建坐席人员月度排班优化问题的二次整数规划模型。鉴于问题模型难解性,依据调研企业需求和模型逻辑结构分析,把问题分解成三个子问题。通过构建整数规划模型和提出启发式算法来求出子问题解,从而生成排班问题优化解。问题实例计算表明,模型算法能够有效控制人力成本和兼顾员工同班次管理目标。与周排班方法比较,该方法能够充分体现月度排班人力灵活性来实现人力优化配置。     

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem

We consider the problem of scheduling n jobs withrelease dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of the optimal nonpreemptive schedule to that of the optimal preemptive schedule is at most 7/3, improving a bound of Shmoys and Wein.     

Scheduling material handling vehicles in a container terminal

Increasing global trade has created the need for efficient container ports. The goal of the port is to move containers as quickly as possible and at the least possible cost. Goods that are delayed at the port are inevitably tardy when delivered to the customer, and thus sanctioned by late charges. Two key activities in the port are (i) unloading of containers from truck and then storage in the export area, and (ii) removal of containers from import storage and then loading onto the trucks. Since containers are large and heavy, specialized material handling vehicles are required for transporting them within the terminal. The focus of this paper is on port terminals where straddle carriers are primarily used to move containers. Container terminals typically have well developed computer and communication networks. Through these networks a terminal scheduler will control and schedule the movement of the straddle carrier fleet in real time. The objective of the terminal scheduler is to minimize the empty travel of straddle carriers, while at the same time minimizing any delays in servicing customers. This paper presents a straddle scheduling procedure that can be used by a terminal scheduler to control the movement of straddle carriers. At its core, the procedure is driven by an assignment algorithm that dynamically matches straddle carriers and trucks, as each becomes available. The procedures were developed and tested in collaboration with the largest container terminal operator in the Port of New York and New Jersey. Using a simulation model of the real system, the superiority of the proposed procedure over two alternative scheduling strategies is illustrated.     

Managing appointments with waiting time targets and random walk-ins

The random arrivals of walk-in patients significantly affect the daily operations of healthcare facilities. To improve the performance of outpatient departments, this paper attempts to make an appointment schedule by considering walk-ins and the waiting time target (WTT) for appointment patients. A stochastic programming model is proposed to solve this problem with the objective of minimizing the weighted patient waiting and makespan cost. A non-decreasing waiting cost function is used to capture the WTT fulfillment of appointment patients, whereas walk-ins incur a linear waiting cost. A finite-horizon Markov Decision Process model is formulated to establish the optimal real-time scheduling policy under a given appointment schedule. The appointment schedule is determined by a two-stage stochastic programming approximation and a local search improvement. Structural properties of the optimal appointment scheduling and real-time scheduling policies are established. In particular, it is shown that appointment overbooking is allowed only at the end of the regular session, and the optimal real-time scheduling policy is an easy-to-implement threshold policy with bounded sensitivity. Numerical experiments based on real data are performed to investigate the influence of different parameters and to compare different schedules. The optimal schedule demonstrates superior performance by allowing reasonable waiting times for appointment patients depending on their WTTs. Managerial insights are also provided to hospital managers. Finally, the basic model is extended by incorporating random service times and random arrivals of appointment patients. The latter includes the random number of patients that show up for service or call for appointments, and the random arrival time (unpunctuality). Appointment overbooking strategies are shown to have different structures under some stochastic factors.     

一个单件车间生产作业计划优化模拟系统

针对中小批量单件车间生产作业计划生成与再生问题,集成Visual Foxpro5.0与Siman 3.51开发了一个系统原型,包括模拟模型生成器、时间参数推算器和禁忌搜索算法。用模拟模型生成器得到一个比较详细的中小批量单件车间生产作业计划方案,以此为初始可行解,再用时间参数推算器和禁忌搜索算法进行优化,得到一个优化了的车间生产作业计划方案。实验表明,本系统较好地解决了中小批量单件车间生产作业计划生成问题。