Which scheduling system assigns patient specific appointment times at regular intervals?

Appointment scheduling systems are widely used in service operations to control the arrival of customers, with the purpose to obtain a steadier arrival process than walk-in systems. In many service systems, when requesting an appointment, customers already know which provider they are going to see, that is, each provider has their own customer queue. As a result, such appointment systems are oftentimes modeled as single-provider systems, where a single provider sees customers according to their appointment time.

However, there are several situations when customers can be seen by any available provider. We refer to these systems as multiple-provider systems with identical providers. In such systems, as far as the appointment scheduling models are concerned, the providers are homogenous/indistinguishable. The difference between a single-provider system and a multiple-provider system with identical providers is that, in the latter, the customer queue is shared among the providers. A case where this happens is when continuity of care is not the primary concern: Balasubramanian, Banerjee, Denton, Naessens, and Stahl (2010) report that customers may prefer seeing “an alternative provider now rather than wait.” Another case where this happens is when only one appointment is needed, for example, appointments at a consulate to request a visa, appointments at an electronic retailer to obtain technical support (e.g., the Apple Genius Bar), or appointments for an initial counseling at a legal center. A third case where this happens is when providers are machines capable of providing the same service, as it is the case for scheduling MRI, CT-scan, or X-ray exams.

Two major complications to model multiple-provider systems are customer no-shows and stochastic service times. No-shows happen when customers fail to show up for their appointment. The observed no-show rates may vary between 4% and 79% (Dantas, Fleck, Oliveira, & Hamacher, 2018). If not addressed properly, no-shows may result in underutilized capacity. A common way to handle no-shows is overbooking, which consists of assigning more than one customer to the same appointment slot (LaGanga and Lawrence, 2012, Liu and Ziya, 2014). While overbooking may increase system productivity and utilization, it may also increase customers’ waiting time and providers’ overtime.

The second major complication to model multiple-provider systems is stochastic service times. Depending on the application and customer type, service times may have different degrees of variability (see Ahmadi-Javid et al., 2017, Cayirli and Veral, 2003, Gupta and Denton, 2008, for a review of applications). Stochastic service times may increase both the uncertainty and customers’ waiting time and providers’ idle time and overtime.

While single-provider systems have been extensively studied in the literature, multiple-provider appointment scheduling systems have been mostly neglected. To the best of our knowledge, no work has been done that addresses both no-shows and stochastic service times for multiple-provider systems with identical providers. The main work that addresses this problem (Zacharias & Pinedo, 2017) assumes deterministic service times; however, this assumption may lead to suboptimal schedules in the presence of variable service times.

In this paper, we develop methodologies to schedule appointments in multiple-provider systems with identical providers in the presence of both no-shows and stochastic service times. We model the system operations over a session as a time-inhomogeneous Discrete Time Markov Chain (DTMC), with the objective of generating an appointment schedule that minimizes the expected total schedule cost per session. The total schedule cost is the sum of three components: customers’ waiting time cost and providers’ idle time and overtime costs. In this paper, we use a day as the session length, but our method works for any valid session length. In our model, session length is divided into slots and appointments are scheduled at the beginning of slots. We assume that customers, who show up, are punctual and walk-ins are not allowed. We also assume that service times follow a discrete distribution and may last 1, 2, …, or T slots. For computational reasons, we choose a value of T=3 in this paper. We show that our three-point discrete service time distribution approximation results in similar-quality schedules to those obtained by using the continuous distribution. We employ this discrete service time distribution in a DTMC framework and compute the value of the objective function exactly, rather than to estimate it through simulation. We then analytically derive some necessary conditions for optimality of a schedule, which dramatically reduce the space of optimal schedule candidates (which we refer to as the “solution space” in the rest of the paper), thus allowing us to identify an optimal or a near-optimal schedule for a large set of problem instances. However, in large problem instances, it may still take a considerable amount of time to explore this reduced solution space. Therefore, we develop a heuristic algorithm, which provides an optimal or a near-optimal schedule in a timely manner. We test our method both on a simulated dataset and a real-world application.

On simulated data, our method leads to schedules with a significantly lower cost than those suggested by existing methods that assume constant service times. The average cost improvement throughout our extensive test suite is 12%; this improvement is higher with lower no-show rates, with more providers, or with higher service time variability. Our experiments also show that when service times are, on average, longer (shorter) relative to the slot length, the optimal schedule tends to have a higher (lower) overbooking level in the first appointment slot.

We also test our method in a real-world application by implementing our schedules at a local counseling center for three months. By applying the schedules that our method generates, the center obtained an average cost reduction of 16%. This reduction is obtained through a dramatic reduction in customers’ waiting time and varying levels of change in providers’ idle time and overtime.

Our contributions are summarized as follows. We develop a methodology to compute the exact value of the objective function for a multiple-provider appointment scheduling problem with stochastic service times and customer no-shows. We prove some optimality conditions for this problem, which are then employed in a complete enumeration procedure to find an optimal or a near-optimal solution. We develop a heuristic method, which has an average performance gap of less than 1% compared to the schedules found through complete enumeration for an extensive test suite. Then, we compare our method to others that assume constant service times; our method leads to an average improvement of 12% in expected total schedule cost and our method never generates a schedule with a higher cost. Finally, we implement our method in a real-world application and results show an average improvement of 16% in total cost.

The remainder of this paper is organized as follows. In Section 2, we briefly review the relevant literature on the multiple-provider appointment scheduling problem. In Section 3, we introduce the notation and develop the modeling steps. Some optimality conditions are discussed in Section 4. Next, in Section 5, we propose a heuristic method and discuss its steps in detail. In Section 6, we present an extensive numerical comparison between our proposed method, best known solutions, and current methods in the literature. In Section 7, we specifically consider a real-world application, and come up with practical schedules that are easy to implement. We highlight the effectiveness of our approach by comparing the pre-post implementation performance in the field. Finally, we conclude our paper in Section 8 with a summary of our results and suggestions for future research directions.

Literature review

Although the problem of scheduling appointments is well studied, the vast majority of the literature focuses on single-provider systems (e.g., Cayirli et al., 2006, Feldman et al., 2014, Gupta and Denton, 2008, LaGanga and Lawrence, 2012, Zacharias and Pinedo, 2014, Zacharias and Yunes, 2018). In addition to systems with only one provider, systems with many providers, each of whom has their own appointment schedule, are also typically modeled as single-provider systems.

There are also a few

Model

We model a multiple-provider appointment scheduling system for a single session (see Table 1 for summary of the important notation). We assume that all P providers are identical in terms of type of customers that they can serve and corresponding service time distributions. The number of providers P, the regular length of a system session per day D, the regular number of appointment slots per session N, and the number of customers to schedule for the session X, are all assumed to be set

Structure of the optimal schedule

We prove the following property regarding the structure of an optimal schedule.

where η=min(N, max{i∈N:⌈iT⌉P<X}+1).

For an optimal policy, this property provides the minimum number of customers to schedule in each slot i, for i=1,…,N, where η∈{1,…,N} is the last slot of the session with customer appointments. If fewer customers were scheduled in slot i < η, then at least one

Heuristic method LBAS

The execution of a complete enumeration procedure, even after reducing the solution space with Proposition 1, can be computationally demanding and hence time consuming for large problem instances. Thus, in this section, in order to find optimal or near-optimal solutions in a short time, we propose a heuristic method, which we call Load-Based Appointment Scheduling (LBAS).

Our LBAS heuristic works with two target load parameters, denoted by ℓ1 and ℓ2. To obtain ℓ1 and ℓ2, we refer to the

Numerical results on simulated data

We now assess the performance of our heuristic method LBAS through two sets of numerical experiments on simulated data. In the first set, we measure the performance gap between the LBAS schedule and the best solution across a wide range of problem instances; in the second set, we compare our method to a state-of-the-art multiple-provider appointment scheduling method.

Real-world experiment

To validate our method, we evaluate the performance of our LBAS heuristic at a local legal counseling center. The center is a non-profit organization which provides access to legal counseling to low-income people. This center receives appointment requests from clients who are seeking legal counseling on one of 35 types of legal problems, such as landlord and tenant disputes, property law, family law, immigration law, and employment law. The managers in this center are interested in a reliable

Concluding remarks

Multiple-provider appointment scheduling systems with identical providers are widely used in service systems where customers are assigned appointment times but they are not assigned a specific provider in advance. Despite their popularity, these systems are not well studied in the appointment scheduling literature. Because of the complexity of the multiple-provider appointment scheduling problem, existing works either assume that all customers show up or that all appointments take the same

Cited by (12)

Recommended articles (6)