In this paper we investigate a stochastic appointment-scheduling problem in an outpatient clinic with a single doctor. The number of patients and their sequence of arrivals are fixed, and the scheduling problem is to determine an appointment time for each patient. The service durations of the patients are stochastic, and only the mean and covariance estimates are known. We do not assume any exact distributional form of the service durations, and we solve for distributionally robust schedules that minimize the expectation of the weighted sum of patients' waiting time and the doctor's overtime. We formulate this scheduling problem as a convex conic optimization problem with a tractable semidefinite relaxation. Our model can be extended to handle additional support constraints of the service durations. Using the primal–dual optimality conditions, we prove several interesting structural properties of the optimal schedules. We develop an efficient semidefinite relaxation of the conic program and show that we can still obtain near-optimal solutions on benchmark instances in the existing literature. We apply our approach to develop a practical appointment schedule at an eye clinic that can significantly improve the efficiency of the appointment system in the clinic, compared to an existing schedule.
In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second-moment matrix of the nonnegative objective coefficients are assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a mixed 0-1 linear program in maximization form with random objective is a completely positive program. This naturally leads to semidefinite programming relaxations that are solvable in polynomial time but provide weaker bounds. The result can be extended to deal with uncertainty in the moments and more complicated objective functions. Examples from order statistics and project networks highlight the applications of the model. Our belief is that the model will open an interesting direction for future research in discrete and linear optimization under uncertainty.
In many production environments, a fixed network of capacity is shared flexibly between multiple products with random demands. What is the best way to configure the capacity of the production network and to allocate the available capacity to meet predetermined fill rate requirements? We develop a new approach for network capacity configuration and allocation and characterize the relationship between the capacity of the network and the attainable fill rate levels for the products, taking into account the flexibility structure of the network. This builds on a new randomized allocation mechanism to deliver the desired services. We use this theory to investigate the connection between the flexibility structure and capacity configuration. We provide a new perspective to the well-known phenomenon that “long chain is almost as good as the fully flexible network”: for given target fill rates, the required capacity level in a long-chain network is close to that in a fully flexible network and is much lower than a dedicated system. We apply these insights and techniques on problems arising in the design of last-mile delivery operations and in semiconductor production planning, using real data from two companies. This paper was accepted by Terry Taylor, operations management.
Resource pooling strategies have been widely used in industry to match supply with demand. However, effective implementation of these strategies can be challenging. Firms need to integrate the heterogeneous service level requirements of different customers into the pooling model and allocate the resources (inventory or capacity) appropriately in the most effective manner. The traditional analysis of inventory pooling, for instance, considers the performance metric in a centralized system and does not address the associated issue of inventory allocation. Using Blackwell’s Approachability Theorem, we derive a set of necessary and sufficient conditions to relate the fill rate requirement of each customer to the resources needed in the system. This provides a new approach to studying the value of resource pooling in a system with differentiated service requirements. Furthermore, we show that with “allocation flexibility,” the amount of safety stock needed in a system with independent and identically distributed demands does not grow with the number of customers but instead diminishes to zero and eventually becomes negative as the number of customers grows sufficiently large. This surprising result holds for all demand distributions with bounded first and second moments. This paper was accepted by Martin Lariviere, operations management.
1 October 2019 in Manufacturing & Service Operations Management
We study the effects of rescheduling on no-show behavior in an outpatient appointment system for both new and follow-up patients. Previous literature has primarily focused on new patients and investigated the role of waiting time on no-show probability. We offer a more nuanced understanding of this costly phenomenon. Using comprehensive clinical data, we demonstrate that for follow-up patients, their no-show probability decreases by 10.9 percentage points if their appointments were rescheduled at their own request, but increases by 6.2 percentage points if they were rescheduled by the clinic. New patients, in contrast, are less sensitive to who initiates rescheduling. Their no-show probability decreases by 2.3 percentage points if their appointments were rescheduled at their own request, and increases by 3.2 percentage points—but is statistically insignificant at the 10% level—if they were rescheduled by the clinic. New patients are more concerned about waiting time compared with follow-up patients. For patients whose appointments were not rescheduled, new patients’ no-show probability decreases by 1.3 percentage points if their waiting time is reduced by one week, but the waiting time has a small and statistically insignificant effect on follow-up patients’ no-show probability. Using data-driven simulation, we conduct counterfactual investigation of the impact of allowing active rescheduling on the performance of appointment systems. In particular, allowing the flexibility of patient rescheduling can reduce the overall no-show rate and increase system utilization, but at a cost of increased wait time for new patients. If patients are able to reschedule at least one week in advance, new patients’ wait time is largely reduced, whereas the no-show rate remains the same; this is equivalent to the effect of a 5% increase in the clinic’s capacity.
1 March 2014 in European Journal of Operational Research