Optimization of Appointment Based Scheduling Systems

Appointment based service systems have been studied widely in the operations research and medical literature over the past three decades. However, the current literature ignores some important aspects of appointment scheduling. In this thesis, we begin by reviewing the existing literature on appointment scheduling with an emphasis on health care applications such as primary and specialty care clinical scheduling, and surgery scheduling. We point out areas in need of further research, particularly focusing on the uncertain nature of customer demand on service systems. We also provide a review of the stochastic programming literature which is relevant to the methodological aspect of this thesis.;We present new stochastic programming models of single server appointment scheduling systems which combine two important aspects of uncertainty: uncertainty in service durations and uncertainty in customer demand. The first model is a static scheduling model with a known number of customers each of which may no-show for their appointment. This problem is modeled as a two-stage stochastic linear program with allowances between customer appointments being the first stage decisions, and customer waiting times and server overtime being the second stage decisions. We provide theoretical properties that give insights into the structure of the optimal appointment schedules, and we present numerical results to demonstrate the effects of cost coefficients and no-show probabilities on the optimal schedule.;The second model considers a dynamic appointment scheduling problem in which an uncertain number of customers request appointments sequentially. The customers are assumed to be scheduled in a sequence that is fixed a priori. This problem is modeled as a multi-stage stochastic linear program in which each stage represents the sequential appointment request of a customer. At each stage, a single appointment decision is made for the appointment time of the new customer. The objective is to minimize expected customer waiting times and overtime. We present a number of methods to improve the efficiency of a decomposition based solution method for this model. Based on the structure of the linear problems at each stage, we adapted an efficient solution method for two variable linear programs. We developed several valid inequalities at each stage to improve bounds and the convergence of the algorithm. We also compared the standard application of nested decomposition method with a special multi-cut implementation of the algorithm. We present numerical results to demonstrate the performances of the different methods and the optimal structure of the resulting appointment schedules.;The third model we present relaxes the assumption of a fixed sequence of customers. We show with a counter-example that a first-come-first-serve based queuing discipline may not be optimal in some scheduling environments. In the presence of different customer types and priorities, the sequencing decisions must be incorporated within the appointment scheduling process. We present a two-stage stochastic integer program which captures the dynamic multistage nature of appointment requests as well as the sequencing of customers. We provide two alternative formulations and tested alternative implementations of the integer L-shaped method. We also present several approaches to tighten the formulation of the subproblems and improve computational efficiency of their solution. Our numerical experiments provide insights on the optimal sequencing and scheduling decisions as well as on the performance of the solution methods.