A Stochastic Approach to Appointment Sequencing

Ph.D. Thesis
Advisor: Dr. Boray Huang
Co-Advisor: Professor Mark Van Oyen (University of Michigan)

Efficiently regulating the arrival of customers through a well-designed appointment system is a critical factor to the performance of many service delivery systems. Among various applications, perhaps the most important application of appointment systems is in healthcare for out-patient and elective surgery scheduling. In this thesis, a useful managerial insight is obtained which could improve the performance of appointment systems in terms of the customers’ waiting times that is a main concern for most healthcare providers.
We study a single server appointment-based queueing system with two classes of customers, regular and fast. The excess service time of a fast customer is stochastically less than that of a regular customer where the excess service time for each customer is defined to be the difference between the service duration and the corresponding job allowance (the length of the appointment slot allocated to the customer). The majority of the appointment scheduling research focus on finding the optimal schedule (appointment times) for either homogeneous customers or heterogeneous customers in a predetermined sequence. Very little is known about the structure of the optimal arrival sequence for various objective functions. In contrast, we focus on finding the optimal arrival sequence to minimize the customer’s waiting time.
We first consider customers with exponential service durations including only one fast customer to provide counter-examples to challenge the Smallest Variance first (SV) and the Shortest Expected Processing Time first (SEPT) rules which are widely conjectured to minimize the customer’s waiting times in the literature. We also provide a sufficient condition to guarantee that SEPT/SV is not optimal as well as a reasonable explanation for this counter intuitive observation by introducing a new concept, voucher effect, in appointment systems.
Moreover, we have observed that the optimal slot for the fast customer is not necessarily the first one, but it is always in the first half of the sequence. Based on this interesting observation, a useful insight is obtained which implies that each fast customer must be scheduled in a position that is in the first half of the positions after the previous fast customer, the First Half Rule (FHR). This sequencing rule is established under the likelihood ratio ordering assumption of the excess service times. In addition, a simple and effective FHR-based heuristic algorithm to completely characterise the optimal sequence is proposed which shows an impressive performance over the test problems.
While the application of the FHR is not limited to appointment systems with constant job allowance, it could be applied to any system with equally spaced appointment times and two classes of customers from a same service distribution family with Monotone Likelihood Ratio Property, for example exponential, beta, Weibull, normal with known variance, uniform, gamma, Poisson, geometric and binomial distributions.
Eventually, we extend our results to address two important practical issues: the server unpunctuality and the customer no-shows. Our results also could be applied to schedule the breaks in an appointment system with equally spaced appointment times as well.