Panel Size and Overbooking Decisions for Appointment-based Services under Patient No-shows Nan Liu • Serhan ZiyaDepartment of Health Policy and Management, Mailman School of Public Health, Columbia University, New York, New York 10032, USA Department of Statistics and Operations Research, University of North Carolina, Chapel Hill, North Carolina 27599, USA [email protected] • [email protected] December 19, 2013 AbstractMany service systems that work with appointments, particularly those in healthcare, suﬀerfrom 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 increaseswith the patient’s appointment delay, i.e., the time between the call for the appointment andthe appointment date. This paper investigates how demand and capacity control decisionsshould be made while taking this relationship into account. We use stylized single serverqueueing models to model the appointments scheduled for a provider, and consider twodiﬀerent problems. In the ﬁrst problem, the service capacity is ﬁxed and the decision variableis 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 netreward function, which reduces to system throughput for the ﬁrst problem. We give partialor complete characterizations for the optimal decisions, and use these characterizations toprovide insights into how optimal decisions depend on patient’s no-show behavior in regardsto their appointment delay. These insights especially provide guidance to service providerswho are already engaged in or considering interventions such as sending reminders in order todecrease no-show probabilities. We ﬁnd that in addition to the magnitudes of patient show-up probabilities, patients’ sensitivity to incremental delays is an important determinant ofhow demand and capacity decisions should be adjusted in response to anticipated changesin patients’ no-show behavior.Key words: service operations; health care management; queueing theory

1 IntroductionPatient nonattendance (commonly known as “no-shows”) at scheduled medical appointmentsis a serious problem faced by many outpatient clinics (Ulmer and Troxler 2004). Patient no-shows not only cause administrative diﬃculties for clinics, but can also lead to disruption ofthe patient-provider relationship and as a result reduced quality of care (Jones and Hedley1988, Pesata et al. 1999). The ﬁnancial loss due to patient no-shows can also be substantial(Moore et al. 2001). Studies have identiﬁed a variety of factors that correlate with patients’no-show behavior. These include patient characteristics such as age, sex, ethnicity, maritalstatus, and socioeconomic status, but also provider related factors such as the physicianscheduled to be seen and the patient’s appointment delay, i.e., the time between the pa-tient’s call for an appointment and the day the appointment is scheduled (Kopach et al.2007, Daggy et al. 2010, Norris et al. 2012, Gupta and Wang 2012). In particular, a strongrelationship between appointment delays and patients’ no-show behavior has been identi-ﬁed in many settings including primary care clinics (Grunebaum et al. 1996), outpatientclinics in academic medical centers (Liu et al. 2010), mental health clinics (Gallucci et al.2005), outpatient OB/GYN clinics (Dreiher et al. 2008), and health care referral services(Bean and Talaga 1995). The main goal of this article is to investigate the optimal demandand capacity control decisions for a clinic which is cognizant of such a relationship. There are mainly two leverages that can be used strategically by clinics to control or atleast inﬂuence appointment delays and thereby reduce the ineﬃciencies caused by no-shows.One is the size of the population (panel size) the physician (or the clinic) is committed toprovide services for (Green and Savin 2008); the other is the number of patients to be seen oneach day via perhaps choosing to overbook (Shonick and Klein 1977, LaGanga and Lawrence2007). These two decisions can be seen as mechanisms that control no-shows indirectly. Manyclinics also engage in practices that directly aim to reduce no-shows. These include sendingreminders one or two days before patient appointments, providing ﬁnancial incentives suchas transport vouchers, and charging ﬁnes to no-show patients. While such interventionsdo not eliminate the no-show problem altogether, they typically have a positive eﬀect (seereview articles such as Macharia et al. (1992) and Guy et al. (2012)). Because patient pop-ulation and baseline no-show rates are diﬀerent, the eﬀects of these interventions may varysigniﬁcantly (Hashim et al. 2001, Geraghty et al. 2007). This paper mainly has two objectives. First, to provide insights into the optimal panel 1

size and capacity/overbooking decisions. Second, to investigate how these decisions shouldbe revised in response to changes in patients’ no-show behavior, which might be a resultof a newly implemented no-show reduction intervention such as those mentioned above.To that end, we adopt the framework used by Green and Savin (2008) and use a stylizedrepresentation of a clinic’s appointment backlog, which views the scheduled appointmentsas a single-server queue. Our objective is not to develop a decision support tool that canreadily be used to make actual panel size and overbooking decisions in practice but ratherto inform such decisions by investigating how the two decisions “should” depend on eachother, system characteristics, and patients’ no-show behavior. Speciﬁcally, we consider two diﬀerent scenarios. First, we assume that the daily servicecapacity is ﬁxed and the clinic does not have the option of overbooking patients. In thisscenario, the only decision variable is the arrival rate of the patients, which can equivalentlybe interpreted as the panel size, and the objective is to maximize throughput, i.e., the long-run average number of patients served per day. For the second scenario, we assume that theclinic’s service capacity is somewhat ﬂexible and thus is a decision variable together withthe arrival rate. This capacity decision can be seen as the clinic’s overbooking decision. Weassume that the clinic has a regular daily capacity, but at extra cost it can make additionalnumber of appointment slots available beyond this capacity on a daily basis. A nominalreward of one is accrued for each patient served. The objective of the clinic is to maximizethe long-run average net reward. For both models, we provide characterizations of theoptimal decisions and investigate how the optimal decisions change with changes in patients’show-up probabilities, which might be predicted in response to one of the newly adoptedinterventions such as sending reminders to patients. One key ﬁnding of our analysis is thatwhen making panel size and overbooking decisions patients’ sensitivity to incremental delays(i.e., how no-show probabilities change with additional delays) may play a more importantrole than the magnitude of the no-show probabilities. One simplifying assumption we make in our mathematical formulation is that patientsneither cancel their appointments nor balk. (A patient is said to balk if s/he chooses notto book an appointment when oﬀered a long appointment delay). Patient cancellation andbalking are commonly observed in practice and there is evidence to suggest that patientsare more likely to cancel or balk when their appointment delays are longer (Liu et al. 2010,KC and Osadchiy. 2012). It is thus natural to suspect that incorporating such eﬀects couldhave changed some of the insights that come out of our analysis. However, our simulation 2

study, which we carried out to investigate this question among others, suggested that thekey insights generated by our mathematical analysis continue to hold even when patientsmay cancel their appointments or balk without making any appointments. Our work is closely related to the operations literature on appointment systems; seeCayirli and Veral (2003) and Gupta and Denton (2008) for in-depth reviews. One way ofclassifying earlier work is according to the type of waiting modeled. Gupta and Denton(2008) deﬁne direct waiting for a patient as the time between the patient’s arrival to theclinic on the day of her appointment and the time the doctor sees her, and indirect waitingas the time between the patient’s request for an appointment and the time of her scheduledappointment. Majority of the work in the appointment scheduling literature deals with directwaiting times mostly focusing on the trade-oﬀ between patients’ waiting time on the day oftheir appointment and physician utilization. Since we study the design of systems in which patients exhibit appointment delay-dependent no-show behavior, we use a formulation that captures patients’ indirect waitingtimes. As Gupta and Denton (2008) discuss, very few articles in the literature deal with indi-rect waiting times. Among the few, Patrick et al. (2008), Gupta and Wang (2008), Liu et al.(2010), Wang and Gupta (2011), and Schu¨tz and Kolisch (2012) all deal with developing ef-fective dynamic scheduling policies to determine whether or not to admit or when to sched-ule incoming appointment requests given the record of scheduled appointments. Among thisgroup of work, the most relevant one to ours is Green and Savin (2008), from which we adoptthe single server queue framework. However, our research questions and the nature of ourcontribution diﬀer signiﬁcantly from theirs. Green and Savin (2008) focus on the panel sizedecisions for a clinic that uses Open Access. In contrast, we are interested in both panel sizeand overbooking decisions that optimize some system-level objective such as throughput orlong-run average net reward. While Green and Savin (2008) develop a model for estimat-ing the largest panel size that an Open Access clinic can handle, we develop analyticallytractable models that lead to useful insights on panel size and overbooking level decisions. The remainder of this article is organized as follows. In Section 2, we introduce our basicformulation and investigate optimal panel size decisions for a clinic that does not overbook.Section 3 builds on the model of Section 2 to incorporate overbooking decisions. In Section4, we report the results of our numerical study. Section 5 provides our concluding remarks.The proofs of all the analytical results can be found in the Online Appendix. 3

2 Panel Size Decisions without an Overbooking OptionWe consider an appointment-based service system (e.g., a primary care clinic) where theservice provider can control the appointment demand arrival rate. In this section, we as-sume that the service provider does not have the option of overbooking appointments andthus the service capacity is ﬁxed. Because our objective is to provide insights on generaldesign questions, following Green and Savin (2008), we assume a macroscopic view of theappointment system and model the scheduled appointments as a single server queue. In therest of the paper, we use the words patient and customer interchangeably.2.1 Model descriptionSuppose that new appointment requests arrive according to a Poisson process with rate λ,and they are scheduled for the earliest available time. We assume that customers do notcancel their appointments, and therefore the new appointment requests join the appointmentqueue from the very end. To better interpret how our model approximates what happensin practice, suppose for now that the length of each appointment slot is deterministic withlength 1/µ. Note that the actual service time of customers may have some variability, but theserver is assumed to be able to ﬁnish the service within 1/µ units of time. Therefore, when anew patient arrives, the service provider can tell the patient precisely when her appointmentis. Our queue is a “virtual” queue for the appointments, a list of scheduled customers. It doesnot empty out at the end of each day. During the times when the clinic is closed, there willnot be any activity in this queue. No one will join and no one will leave. Therefore, we canignore those “dead” periods, merge the time periods during which the appointment queue isactive, and carry out a steady-state analysis with the understanding that time is measuredin terms of work days and work hours. Note that in our model, customer waiting time is notdetermined by waiting in the clinic (called direct waiting) but by waiting elsewhere for theday and time of the appointment to come (called indirect waiting). When the time for the patient’s appointment arrives, the patient may not show up.However, if she shows up, she shows up on time. We assume that whether or not a customershows up for her appointment depends on the number of customers ahead of her, i.e., theappointment queue length, upon the arrival of her request for appointment.1 Consider a 1The queue length at the appointment time serves as a proxy for the delay that the patient will experience.Note that there is no one-to-one relationship between the queue length at the time of an appointment request 4

customer who ﬁnds j ∈ Z scheduled appointments in the queue (including the customer inservice), where Z denotes the set of non-negative integers. We use pj ∈ [0, 1] to denote theprobability that this customer will show up for her appointment. It is possible that some ofthese j customers ahead of her may not show up for their appointments, but this does notchange the fact that this new customer will have to “wait” for j appointment slots to passbecause she will not show up at the clinic until her scheduled appointment time (if she showsup at all). (It might be helpful for the reader to view the server of this queue as “serving”appointment slots as opposed to patients. The server does not idle when the appointmentis a no-show, it ”serves” the no-show appointment slot. Serving the appointment slot takesthe same amount of time regardless of whether the holder of that appointment slot showedup or not and therefore the waiting time of a new patient is determined by the number ofcurrently scheduled appointment slots.) Motivated by empirical studies (see, e.g., Grunebaum et al. 1996) which ﬁnd that thelength of a patient’s appointment delay is positively correlated with her no-show probability,we assume that pj ≥ pj+1 for j ∈ Z and let p∞ = limj→∞ pj. To avoid a trivial scenario,we also assume that there exists 0 < j < k such that pj > pk, which also implies thatp0 > 0. We assume that for every scheduled customer who shows up, the system accrues onenominal unit of reward. If a scheduled patient does not show up or there are no scheduledpatients in the queue, the provider might be able to ﬁll in the slot by a walk-in patientwho also leaves a reward of one. If neither a scheduled nor a walk-in patient appears inan appointment slot, the provider collects zero reward. We assume that the probability ofsuccessfully ﬁlling in an empty slot by a walk-in patient is ξ independently of the systemstate. This assumption is a better ﬁt in cases where the clinic has dedicated providers toserve walk-ins. For example, in two large community health centers, each of which servesmore than 26,000 patients annually in New York City, walk-in patients are seen by providerswho exclusively see walk-ins and may be diverted to physicians who see scheduled patientsonly when some of these scheduled ones do not show up (Rosenthal 2011, Fleck 2012). Toavoid an unrealistic and trivial scenario, we assume that ξ ∈ [0, 1). Deﬁning qj as the probability that the appointment slot assigned to a patient who seesarrival and the expected delay until the appointment. In particular, the expected delay for any two patientswho see the same number of appointments upon their request may be diﬀerent in practice because of thetimes (e.g., nights and weekends) during which the clinic will be closed. However, for a clinic which seesthe same number of patients everyday, the diﬀerence is guaranteed to be less than one workday under theassumption that the clinic is open all workdays. 5

j appointments ahead will not be wasted (i.e., used by either that particular patient or awalk-in), we have qj = pj + (1 − pj)ξ. (1)We call {qj, j = 0, 1, . . . } ﬁll-in probabilities. Then, qj+1 = ξ +(1−ξ)pj+1 ≤ ξ +(1−ξ)pj = qj,which in turn implies that the limit of qj as j → ∞ exists. We use q∞ to denote this limit. Deﬁne Πj(λ, µ) to be the steady-state probability that there are j appointments in thequeue including the ongoing service (which may actually be a “no-show service”). Let T (λ, µ)denote the long-run average reward that the system will collect and ρ = λ/µ be the traﬃcintensity in the system. Then, we can write ∑∞ (2) T (λ, µ) = λ Πj(λ, µ)qj + µ(1 − ρ)ξ. j=0The ﬁrst term on the right side of (2) is the reward obtained from patients who show upfor their scheduled appointments and walk-in patients who are served in place of no-showpatients. From PASTA (e.g., Kulkarni (1995)), Πj(λ, µ) is the probability that there arej scheduled appointments at the arrival time of a new appointment in steady state andwith probability qj this appointment will be ﬁlled in either by the patient who makes theappointment or a walk-in patient in case of a no-show. The second term is the rewardobtained from walk-in patients when there are no scheduled patients in the queue. To seethat, we note that the steady-state probability that the server has no scheduled customerswaiting is 1 − ρ. That is, in the long run, µ(1 − ρ) slots per day have no scheduled customersin them. Since each of these slots will be ﬁlled by a walk-in with probability ξ, the long-runaverage reward rate accrued from these slots is µ(1 − ρ)ξ. Because appointment arrivals occur according to a Poisson process and time spent on eachappointment is deterministic, the appointment queue can be modeled as an M/D/1 queue.One can numerically compute the steady state distribution for this queue, i.e., {Πj(λ, µ)}j∞=0but we do not have a closed-form expression and as a result it is very diﬃcult if not impos-sible to carry out mathematical analysis and establish structural properties. To overcomethis problem, we approximate the steady-state probabilities assuming that service times areexponentially distributed, i.e., the appointment queue is an M/M/1 queue. For the M/M/1 queue, it is well-known that (e.g., Kulkarni (1995)) Πj(λ, µ) = (1 − ρ)ρj, ∀j ∈ Z, (3) 6

if ρ = λ/µ < 1. Then, using (1) and (3), one can write (2) as ∑∞ (4)T (λ, µ) = (1 − ξ)λ (1 − ρ)ρjpj + µξ. j=0Let W denote the waiting time (appointment delay) for a random customer before her servicein steady state (regardless of whether the customer shows up or not). It is well known thatin an M/M/1 queue with an arrival rate of λ and service rate of µ such that λ < µ,E(W ) = λ . (5) λ) µ(µ − The service provider’s objective is to maximize the long-run average reward collected,by choosing the appointment demand rate λ for a ﬁxed service capacity µ while makingsure that the expected delay (time until appointment for a newly arriving patient) does notexceed a prespeciﬁed level κ. Thus, under the M/M/1 approximation, the optimal λ can befound by solving the following optimization problem:max0≤λ≤µ T (λ, µ) (P1)s.t. E(W ) ≤ κ.with T (µ, µ) deﬁned as T (µ, µ) = limλ→µ T (λ, µ) = µ[ξ + (1 − ξ)p∞] = µq∞ (see Lemma1 in the appendix) and E(W ) = ∞ for λ = µ. Note that the long-run average rewardT (λ, µ) = T (µ, µ) for any λ > µ and therefore one can restrict attention to λ ∈ [0, µ] inproblem (P1). That is, the optimal panel size will never lead to an overloaded system, wherethe arrival rate exceeds the service rate even when κ = ∞.In the following, we provide characterizations of the optimal arrival rate for a ﬁxed valueof service capacity with and without a service level constraint on the expected appointmentdelay, and investigate how these optimal arrival rates change with customers’ show-up prob-abilities. As in Green and Savin (2008), if one assumes that each individual in the panel callsto make an appointment with an exponential rate λ0, choosing λ is equivalent to choosingthe panel size N = ⌊λ/λ0⌋ where ⌊x⌋ is the integer part of x. Thus, our results for theoptimal arrival rate have direct interpretations in the context of optimal panel size decisions.Table 1 summarizes our notation some of which will be introduced in Section 3.2.2 Characterization of the optimal panel sizeWe ﬁrst investigate how the reward function T (λ, µ) changes with the arrival rate λ and givea characterization of the unique optimal arrival rate for Problem (P1) for a given µ. 7

Table 1: Notation used in the paper.Symbol Descriptionλ0 Individual patient demand rateN Panel sizeλ Total patient demand rate, λ = N λ0µ Provider service rateρ Traﬃc intensity, ρ = λ/µpj Show-up probability when a patient sees j patients ahead of her upon her arrivalξ Probability of ﬁlling a no-show slot by a walk-inqj Probability that an appointment slot booked by an arriving patient who sees j patients in the system upon her arrival is not wasted, qj = pj + (1 − pj)ξΠj(λ, µ) The steady-state probability that an arrival sees j appointments in the queueT (λ, µ) The long-run average throughput rateW The appointment delay for a random customer before her service in steady stateκ Maximum allowed value for the expected appointment delayλ1∗ The optimal demand rate when overbooking is not an optionρ∗1 The optimal traﬃc intensity when overbooking is not an option, ρ∗1 = λ∗1/µω(µ) Daily cost function when the daily service rate of the clinic is set to µM Regular daily capacity of the service providerR(λ, µ) The expected daily net reward for the service provider in steady-stateΛ(ρ) Eﬀective server utilization when the traﬃc intensity is ρλ∗2 The optimal demand rate when overbooking is an optionµ∗2 The optimal overbooking levelρ∗2 The optimal traﬃc intensity when overbooking is an option, ρ∗2 = λ∗2/µ2∗Proposition 1 For λ ∈ [0, µ], the long-run average reward T (λ, µ) is a strictly concavefunction of λ and hence T (λ, µ) has a unique maximizer denoted by λ¯1. In addition, if thereexists τ ∈ (0, 1) such that ∑∞ (6) p0 + (j + 1)τ j(pj − pj−1) = 0, j=1then λ¯1 = µτ ; otherwise, T (λ, µ) is strictly increasing in λ ∈ [0, µ] and λ¯1 = µ. Thus, whenκ = ∞, the unique solution to (P1), λ∗1 is given by λ¯1; otherwise it is given by min{λb, λ¯1}where λb = κµ2 is the arrival rate for which the constraint on the expected waiting time is κµ+1satisﬁed as an equality. Let ρ1∗ = λ∗1/µ denote the optimal traﬃc load for Problem (P1) for ﬁxed µ or equivalentlythe optimal utilization, i.e., the fraction of time the physician is scheduled to see patients. 8

One important observation we can make from Proposition 1 is that the walk-in probabilityξ has no eﬀect on the optimal panel size. If there is no restriction on the expected delay, i.e., κ = ∞, the optimal traﬃc load isindependent of the service capacity. In this case, when the appointment delays do not havea signiﬁcant impact on customers’ show-up probabilities, we have ρ1∗ = 1. If, however, theno-show rate drops fast as the appointment delay increases, then there exists an optimalarrival rate, which is strictly less than the service rate, i.e., ρ∗1 < 1. Thus, even when thereis no restriction on the expected waiting time, the service provider does not prefer demandto be as high as possible since high demand would lead to long waiting times, which in turnwould result in low show-up rates diminishing the system reward rate. Low demand rateswould lead to high show-up rates, but clearly, the service provider would not want to set itso low as to cause the server idle frequently. Thus, there is an ideal value for the arrival rate(an ideal panel size for a healthcare clinic) that helps the system hit the “right” balance.2.3 Eﬀects of introducing policies to improve show-up probabili- tiesIn this section, we investigate how the panel size should be adjusted in response to the adop-tion of a new policy, which is expected to change customers’ show-up rate. As we discussedin Section 1, such policies include making reminder phone calls, sending text messages oremail reminders, providing ﬁnancial incentives, and charging no-show fees. Speciﬁcally, weinvestigate how the optimal panel size changes with the show-up probabilities p = {pj}∞j=0. Consider the service system described in Section 2.1 with show-up probabilities denotedby {pj}∞j=0. Suppose that once the new policy is adopted, the only change will be in customershow-up probabilities, which we will denote by {pˆj}∞j=0. Also, suppose that once the newpolicy is adopted, customers are more likely to show-up, i.e., pˆj ≥ pj for all j ∈ Z. Now,when is the optimal panel size larger, before the new policy takes eﬀect or after? Moreprecisely, letting λˆ1∗ denote the optimal arrival rate when show up probabilities are given by{pˆj}∞j=0, which one is larger, λ∗1 or λˆ1∗? There are two diﬀerent ways of coming up with an answer to this question based on intu-ition. First, if patients are more likely to show up under the new policy, i.e., the probabilityof showing up is higher for any given queue length, the provider might tend to believe thatthe clinic can handle more patients eﬀectively (after all there is less loss of eﬃciency due tono-shows) and choose to increase its panel size. Alternatively, one might argue that because 9

patients are more likely to show up, the expected load per patient on the system is higherand thus there is less incentive to admit more patients. Consequently, the optimal panel sizeshould be lower. As it turns out, both of these arguments are ﬂawed. The answer is a littlemore subtle. First, consider the following simple example:Example 1 Suppose that µ = 20, ξ = 0, and κ = ∞. Let pj = (0.9)j+1 for j ∈ Z; pˆ0 = 1,pˆ1 = 0.9, and pˆj = (0.9)j+1 for j ∈ {2, 3, . . . }. Thus, pˆj ≥ pj for all j ∈ Z. But, onecan show that λ∗1 = 15.19 while λˆ∗1 = 14.95. (In the M/D/1 setting, λ1∗ and λˆ1∗ are 16.24and 15.97, respectively.) That is, the optimal panel size is smaller when customers are morelikely to show up.In Example 1, the optimal reward rate increases from 10.39 to 11.01 (from 11.51 to 12.17 inthe M/D/1 setting) when p increases to pˆ. In fact, more generally, one can prove that forany ﬁxed λ the reward rate under pˆ is always larger than that under p if pˆj ≥ pj for all j.However, when patient show-up probabilities increase, increasing the panel size in responsemay actually result in lower reward rate. This shows that our ﬁrst intuitive reasoning, whichwe discussed above, is incorrect. What really matters when determining the optimal loadon the system is the marginal sensitivity of customers’ show-up probabilities to incrementalchanges in appointment delays. It is possible that even though customers are more likely toshow up, they might have become relatively more sensitive to incremental changes in theirdelays and this might cause the service provider to try to keep the queue lengths shorterthan they used to be. Now, consider the following condition:Condition 1 pˆj+1pj ≥ pj+1pˆj for all j ∈ Z.When pj > 0 and pˆj > 0 for all j, the condition above is equivalent to pˆj+1 ≥ ,pj+1 which pˆj pjessentially says that show-up probabilities under the new system are less sensitive to addi-tional delays since the percentage drop for additional waiting is always less under the newsystem. It turns out that Condition 1 is suﬃcient to ensure that the optimal panel size islarger under the new system.Proposition 2 Under Condition 1, λˆ1∗ ≥ λ1∗. In other words, the optimal panel size is largerwhen customer show-up probabilities are less sensitive to additional appointment delays. 10

Proposition 2 makes it clear that what matters for the panel size decision is the customers’sensitivity to delays. In Example 1, Condition 1 holds in the opposite direction becausepj+1 = 0.9, but pˆj+1 = 0.9 for j = 0, 2, 3, . . . and pˆ2 = 0.81. Therefore, it is not surprising pj pˆj pˆ1for the optimal panel size to drop under the new show-up probabilities. Proposition 2 alsoimplies that the intuitive argument that the optimal panel size should decrease when show-upprobabilities increase is incorrect because one can easily come up with examples in which theshow-up probabilities satisfy Condition (1) and pˆj ≥ pj for all j. In short, our analysis in this section suggests that with a new intervention that is stronglyexpected to improve patient show-up rates, providers would realize higher patient throughputif they do not change their panel size. However, one should be careful when choosing a newpanel size in order to further beneﬁt from changes in show-up probabilities since changesbased on one’s intuition alone might be counterproductive. It appears that, it is particularlyimportant for the service provider to get a good sense of how the customers’ sensitivitiesto additional delays will change with the new intervention. If the intervention helps reducecustomer sensitivity to additional delays, then our results suggest that there is room forfurther improvement in throughput by increasing the panel size.3 Joint Panel Size and Overbooking Level DecisionsOne approach clinics use in order to improve the utilization of the appointment slots isto book more appointments than the clinic’s regular daily capacity typically allows. In thissection, we assume that in addition to the panel size, the service provider can also choose thenumber of appointments scheduled per day. We model this in a stylized manner by makingservice rate (i.e., number of appointments scheduled per day) another decision variable inaddition to the arrival rate.3.1 Description of the modelThe assumptions regarding the arrival of the appointment requests, service, and customerno-show behavior are the same as those for the model described in Section 2.1. In orderto integrate overbooking and panel size decisions, we adopt a reward/cost formulation thatis similar to the one used in Liu et al. (2010). Speciﬁcally, we assume that for every ﬁlledappointment slot, the service provider collects a nominal reward. The daily cost incurredto the clinic is a function of the service rate µ it sets, i.e., the number of appointments 11

scheduled per day. We use ω(µ) to represent this cost function. We assume that there is aﬁxed cost of operating the clinic independently of the service rate chosen by the clinic andwe assume that this cost is zero without loss of generality. As for the variable cost, we letM ≥ 0 be the regular daily capacity of the clinic and thus max{0, µ − M } can be thoughtof as the overbooking level. We assume that there is a cost if the clinic chooses to go abovethis capacity. This cost can be seen as the direct ﬁnancial cost (e.g., overtime cost for thestaﬀ) and/or the indirect cost of patient dissatisfaction as a result of long waits on the day ofthe appointment and less time devoted to the care of each patient. Intuitively, the more theclinic overbooks, the higher this cost would be; in addition, it seems reasonable to assumethat this cost increases faster at a higher overbooking level. Thus, we assume that ω(µ) = 0if µ ≤ M , ω(·) is continuous on [0, ∞), strictly increasing and strictly convex on [M, ∞),and twice diﬀerentiable on (M, ∞). Let R(λ, µ) denote the expected daily net reward for the service provider. Then, ∑∞ (7)R(λ, µ) = T (λ, µ) − ω(µ) = (1 − ξ)λ (1 − ρ)ρjpj + µξ − ω(µ) j=0where T (λ, µ) is given by (4). The objective of the service provider is to choose the arrivaland service rates which maximize R(λ, µ) while enforcing the expected appointment delayto remain below a certain level κ. Then, our problem (P2) can be written asmaxλ,µ:0≤λ≤µ R(λ, µ) (P2)s.t. E(W ) ≤ κwith R(µ, µ) deﬁned as R(µ, µ) = limλ→µ R(λ, µ) = µq∞ − ω(µ) and limλ→µ E(W ) = ∞.3.2 Characterization of the optimal solutionIn this section, we establish some structural properties of the optimal solution to Problem(P2). We ﬁrst study the model without the service level constraint, i.e., setting κ = ∞. Weknow from Proposition 1 that for a ﬁxed µ, there exists a unique value of λ that maximizesthe reward T (λ, µ). We denote this optimal value by λ(µ). Then, maximizing R(λ, µ) withrespect to λ and µ is equivalent to maximizing R(λ(µ), µ) with respect to µ only. Let λ¯2 and µ¯2 denote the optimal values for λ and µ in Problem (P2) without the waitingtime constraint. From Lemma 2, which is provided in the Appendix, we know that for0 ≤ µ ≤ M , R(λ(µ), µ) is a linear and strictly increasing function of µ, which immediatelyimplies that the optimal service rate is no less than the regular daily capacity, i.e., µ¯2 ≥ M . 12

This is not surprising since there is no incentive for the service provider not to use thecapacity that is already available with zero additional cost. In order to derive a completecharacterization of λ¯2 and µ¯2, we rewrite the reward function T (λ, µ) as follows T (λ, µ) = µΛ(ρ),where ∑∞ Λ(ρ) = (1 − ξ) (1 − ρ)ρj+1pj + ξ. (8) j=0Hence Λ(ρ) can be regarded as the “eﬀective” server utilization (proportion of time the serveris busy with serving patients, either scheduled ones who actually show up or walk-ins) whenthe traﬃc intensity, λ/µ equals ρ. Let ω+(µ) denote the right derivative of ω(µ). Then, ω+(µ) is a strictly increasing func-tion for µ ∈ [M, ∞) and it has an inverse, denoted by (ω+)−1(·), which is also strictlyincreasing in its domain. Let ρ¯1 denote the optimal traﬃc intensity for Problem (P1) whenκ = ∞. Recall that ρ¯1 does not depend on µ. Hence, Λ(ρ¯1) is the eﬀective server utilizationwhen system throughput (i.e., long-run average rate at which patients are served) is max-imized when there is no restriction on the expected waiting time. Then we can prove thefollowing proposition.Proposition 3 Suppose that κ = ∞, i.e., there is no restriction on the expected appointmentdelay. Then, given the show-up probability vector p = {pj}j∞=0, the optimal service rate µ¯2and arrival rate λ¯2 for Problem (P2) take the following form: if ω+(µ) ≤ Λ(ρ¯1), ∀µ ≥ M , ∞ if ω+(M ) ≥ Λ(ρ¯1), µ¯2 = M otherwise, (ω+)−1(Λ(ρ¯1))and λ¯2 = ρ¯1µ¯2. Furthermore, (λ¯2, µ¯2) is the unique optimal solution to problem (P2). The expression for µ¯2 provided in Proposition 3 may seem technical but in fact it hasa straightforward interpretation. Notice that ω+(µ) is the marginal cost of additional unitcapacity when the service capacity is µ. The service provider would be willing to increasethe service capacity (and the arrival rate along with it) up to the point where marginalcost equals the rate with which the system generates revenue, which is equal to the eﬀectiveserver utilization. This corresponds to the third case in the statement for µ¯2 in Proposition3. However, if the marginal cost is below this revenue generation rate no matter what the 13

service capacity is (which is unlikely in practice), then there is no point in restricting thenumber of people to be seen on a given day and thus µ¯2 = ∞. If the marginal cost is highereven at the regular capacity, then there is no incentive to overbook and thus µ¯2 = M . Next, we consider problem (P2) with a non-trivial service level constraint, i.e., κ < ∞.Corollary 1 If κ < ∞ and there exists a ﬁnite µ such that ω+(µ) > 1, then there exists aﬁnite optimal value for µ.The condition given in Corollary 1 essentially implies that as one adds more appointmentsfor a given day there is a certain level beyond which the incremental beneﬁt of havingone more appointment is outweighed by its incremental cost. Suppose that this realisticcondition holds. It is not possible to obtain closed-form expressions for optimal arrival andservice rates. However, we can show that optimal rates possess some convenient structuralproperties, which can be helpful in devising simple solution methods. Let (λ∗2, µ2∗) denotean optimal arrival and service rate pair when there is a constraint on the expected waitingtime. Then, we can show the following. { ρ¯1 if ρ¯1 < 1, if ρ¯1 = 1.Proposition 4 Let γ be deﬁned as γ = κ(1−ρ¯1) Then, for a ﬁxed show-up ∞probability vector p = {pj}, if γ < µ¯2, then µ2∗ = µ¯2 and λ∗2 = λ¯2. Otherwise, µ∗2 ≤ γ andthe service level constraint is binding at optimality, i.e., λ2∗ = 1− .1 µ2∗ κµ∗2 +1 Proposition 4 suggests a relatively easy way to obtain an optimal solution. If γ < µ¯2, thenthe optimal solution is given by the optimal solution to (P2) with no service level constraints,which is directly available from Proposition 3. If γ ≥ µ¯2, then the problem reduces to anoptimization problem with a single decision variable since in this case λ2∗ can be expressedexplicitly in terms of µ2∗. More speciﬁcally, an optimal service rate can be obtained by solvingthe following optimization problem: max Rb(µ) (9) µ≥0where 1 ∑∞ 1 1 j κµ + ( κµ + Rb(µ) = (1 − ξ)µ(1 − ) κµ + )(1 − ) pj + µξ − ω(µ). (10) 1 1 1 j=0Consider the nontrivial case where ρ¯1 < 1. When κ = ∞ meaning that there is no restrictionon the expected delay, γ = 0. Consequently, µ∗2 = µ¯2 and λ∗2 = λ¯2, as expected. 14

Since Rb(µ) deﬁned in (10) is not necessarily unimodal in µ, multiple optimal solutionsmay exist. Therefore, in the following, we shall refer to µ∗2 as the smallest optimal servicerate, i.e., µ∗2 = inf{µo : Rb(µo) ≥ Rb(µ) for all µ ≥ 0}. Then, we know from Proposition 4that the corresponding optimal arrival rate λ∗2 and the optimal traﬃc load deﬁned as ρ∗2 = λ2∗ µ∗2are also the smallest choices for these two variables.3.3 Eﬀects of introducing policies for improving show-up proba- bilities and changing the service level requirementIn this section, we investigate the sensitivity of the optimal panel size and overbookingdecisions (optimal arrival and service rates in our formulation) to customers’ show-up prob-abilities and κ, the service level requirement on the expected waiting time. In Section 2.3,we showed that when overbooking is not an option and there is a ﬁxed daily capacity, theoptimal panel size is larger when customers’ show-up probabilities are less sensitive to ad-ditional delays. When overbooking level is also a decision variable together with the panelsize, it is not clear how “improvements” in show-up probabilities would aﬀect the optimaldecisions. When show-up rates of appointment slots are less sensitive to additional delays,does that mean that the service provider has less incentive to overbook since there is lessuncertainty regarding whether or not the scheduled appointments will actually be ﬁlled?As for the panel size, if the optimal overbooking level is higher, intuition suggests that theoptimal panel size would be larger as well but it is diﬃcult to predict how it would changeotherwise. In any case, we ﬁnd that the optimal panel size and overbooking level mightchange in unpredictable ways. We ﬁrst investigate the sensitivity of the optimal decisions to show-up probabilities.As in Section 2.3, suppose that as a result of a new policy that aims to improve show-uprates, customer show-up probabilities {pj}∞j=0 become {pˆj}∞j=0 and let λˆ∗2 and µˆ∗2 respectivelydenote the optimal demand and service rates under this new policy (the smallest optimalvalues in the unlikely event that there are multiple optimal solutions). Then, we can provethe following proposition:Proposition 5 If pˆj ≥ pj for all j ∈ Z, then µˆ2∗ ≥ µ∗2. If pˆj ≥ pj for all j ∈ Z and Condition1 holds (i.e., pˆj+1pj ≥ pj+1pˆj for all j ∈ Z), then λˆ2∗ ≥ λ∗2, µˆ2∗ ≥ µ2∗, and ρˆ∗2 ≥ ρ2∗, whereρ∗2 = λ2∗ and ρˆ2∗ = .λˆ∗2 µ∗2 µˆ2∗ 15

Remark 1 In the second part of Proposition 5, it is suﬃcient to assume that pˆ0 ≥ p0(instead of pˆj ≥ pj for all j ∈ Z) together with Condition 1. According to Proposition 5, if customers are more likely to show up under the new policy,the service provider chooses to increase the overbooking level. There is a cost of workingwith a higher overbooking level but the service provider knows that appointment slots aremore likely to be ﬁlled in and thus the system is more likely to beneﬁt from an increasein the capacity. However, it turns out that even if the service provider chooses to work ata higher overbooking level, it does not mean that she would choose to work with a largerpanel as well (see Example 2 below). A larger panel size and a higher overbooking level arenot guaranteed to be optimal when customers are more likely to show up. These show-uprates also need to be less delay sensitive for the service provider to choose both a higheroverbooking level and a larger panel size.Example 2 Suppose that p0 = 0.4 and pj = 0.38 for all j ≥ 1, and pˆ0 = 1 and pˆj = 0.4for all j ≥ 1. Let ξ = 0, κ = ∞ and ω(µ) = aµ2 where a is a positive constant. Then,T (λ, µ) = λ[0.4(1−ρ)+0.38ρ] = µ(0.4ρ−0.02ρ2). For a ﬁxed µ, T (λ, µ) is strictly increasingin ρ ∈ [0, 1]. Hence ρ¯1 = 1 and R(λ(µ), µ) = 0.38µ − aµ2. It then follows that λ∗2 = µ2∗ = 19 . Now, note that Tˆ(λ, µ) = λ[(1 − ρ) + 0.4ρ] = µ(ρ − 0.6ρ2). Hence λˆ∗2 = 5 µˆ2∗, and100a 6Rˆ(λ(µ), µ) = 5 µ − aµ2. It follows that µˆ∗2 = 5 > µ2∗ = 19 as expected since pˆj > pj for 12 24a 100aall j; however, λˆ∗2 = 5 × 5 = 25 < λ∗2 = 19 and ρˆ2∗ = 5 < 1 = ρ2∗. 6 24a 144a 100a 6 Next, we investigate how changes in the service level requirement, which is determinedby κ, aﬀect the optimal decisions. For example, if the service provider commits herself toproviding customers shorter waiting times, how should she adjust the panel size and thedaily overbooking level? Intuition suggests that because the goal is to reduce the averagewaiting time, a reasonable adjustment would be to reduce the panel size and increase theoverbooking level appropriately. Interestingly however, that is not necessarily the case. Asan example, suppose that pj = 0.99j for j ∈ Z and ω(µ) = 0.01µ2. In this case, Figure 1shows how the optimal demand rate λ2∗, the optimal service rate µ2∗, and the optimal traﬃcload ρ∗2 = λ2∗ change with the service level parameter κ which varies from 0.07 to 0.27. Recall µ∗2that κ is the allowable maximum value set by the provider for the average waiting time ofscheduled customers. One can observe that the optimal arrival rate and service rate are notmonotone in κ. Interestingly, for small values of κ, the optimal decision is to increase the 16

overbooking level even as the service level requirement gets less restrictive, i.e., as κ getslarger (see Figure 1b). However, for suﬃciently large values of κ, the optimal panel sizedecreases with less restriction, i.e., with larger κ (see Figure 1a). Figure 1a Figure 1cOptimal arrival rate (λ2*) 38 0.12 0.17 0.22 Optimal traffic intensity (ρ2*) 0.92 37 0.9 36 κ 0.27 35 Figure 1b 0.88 34 0.86 33 0.84 0.07 0.82 45 0.8 0.78Optimal service rate (µ2*) 44 43 42 0.76 41 0.74 0.07 0.12 0.17 0.22 0.27 0.07 0.12 0.17 0.22 0.27 κ κFigure 1: The optimal decisions and traﬃc intensity vs. service level parameter κ. In Figure 1c, we observe that, unlike the optimal arrival and service rates, the optimaltraﬃc load behaves as expected. It is monotonically increasing in κ. In fact, this behavioris not exclusive to this particular example and Proposition 6 proves that the optimal loadρ∗2 is an increasing function of κ.Proposition 6 The optimal traﬃc load ρ2∗ increases as the service level requirement becomesless restrictive, i.e., ρ2∗ increases with κ.According to Proposition 6, if the provider works with a less strict service level, the load onthe system, and as a result expected length of the appointment queue will increase under theoptimal policy. However, as our earlier example demonstrates, this does not mean that theclinic will actually be serving a larger panel of patients since from the clinic’s point of view,it might be preferable to decrease both the panel size and overbooking level appropriately. 17

Finally, in this section we investigate how the optimal panel size and overbooking levelchange with walk-in probability ξ. When overbooking is not an option, we found that thewalk-in probability has no eﬀect on the optimal panel size. However, it turns out that whenoverbooking is an option, higher walk-in probabilities not only lead to higher overbookinglevels but also larger panel sizes and traﬃc intensities.Proposition 7 When ξ increases, the optimal demand rate λ∗2, the optimal overbooking levelµ2∗ and the optimal traﬃc intensity ρ2∗ for problem (P2) increase. When the probability that an appointment slot is not wasted is higher, overbooking ismore likely to beneﬁt the clinic and thus the optimal overbooking level is higher. Thisresult may seem counterintuitive at ﬁrst. After all one reason clinics overbook is to alleviatethe eﬀect of no-shows on the system. However, one should note that the increase in theoverbooking level is mainly due to the fact that the panel size is also a decision variable.When the overbooking level is higher the clinic can handle more patients on a daily basis andtherefore the optimal panel size is also larger. In fact, it turns out that the fractional changein the optimal panel size is larger than the fractional change in the optimal overbookinglevel, leading to a larger traﬃc load. When the no-show slots are more likely to be ﬁlled inby walk-ins, the clinic can handle a larger load eﬃciently. In summary, lower no-show rates will always help if one is willing to keep the samepanel size and overbooking level. There is room for further improvement if the provideris willing to make some changes. However, our analysis in this section suggests that oneneeds to be careful when choosing a new panel size and overbooking level as it might havesome unexpected consequences. For example, even though a lower no-show rate encouragesthe provider to see more patients in a day, it does not mean that the provider shouldincrease the panel size. Only when patient sensitivity to additional delays also decreases,a larger panel size would necessarily be more beneﬁcial. On a separate note, our resultsalso point to interesting relationships among expected appointment delay (the service levelrequirement), optimal panel size, and overbooking level. As it turns out, requiring theexpected appointment delay to be lower may lead to a larger optimal panel size or a loweroverbooking level. Before we move on to the description and discussion of our numerical study, it might behelpful to provide a summary of our key analytical ﬁndings established in Sections 2 and3. In particular, Table 2 sorts out the conditions needed for the optimal panel size and 18

Table 2: Summary of the key insights. The second column indicates the changing direction ofthe optimal panel size N ∗ (when only the panel size can be chosen) in diﬀerent scenarios. Thethird column shows the changing directions of both the optimal panel size and overbookinglevel (N ∗, µ∗) when both can be chosen. “↑”, “↓” and “?” respectively mean “increases,”“decreases,” and “no deﬁnite answer.”Scenarios N ∗ (N ∗, µ∗)No-show rate ↓ ? (?, ↑)Sensitivity to delay ↓ ↑ (?,?)No-show rate ↓ & Sensitivity to delay ↓ ↑ (↑,↑)overbooking level to be larger depending on whether only the former or both can be freelydetermined by the service provider.4 Numerical StudyIn this section, we report the ﬁndings of our extensive numerical study conducted to in-vestigate whether the insights obtained using our analytical model depend on some of thekey modeling assumptions (Sections 4.1 and 4.2) and also how the panel sizes that are op-timal according to our formulation compare with those that are determined to be ideal forimplementing Open Access in the literature (Section 4.3).4.1 Comparison of the M/M/1 and M/D/1 modelsSo far in this paper, mainly for analytical tractability, we assumed that the appointmentqueue can be modeled as an M/M/1 queue. In some respects, however, the M/D/1 queuecan seem like a more ﬁtting choice. This is mainly because in our formulation the server isessentially “serving” appointment slots whose lengths are deterministic. It is thus of interestto investigate whether the results would change signiﬁcantly if the appointment queue wereassumed to operate as an M/D/1 queue. First, it is important to note that as we havealready indicated, Example 1 demonstrates that under both the M/M/1 and the M/D/1setup, having patients who are more likely to show-up does not mean that the optimal panelsize is also larger. Thus, our numerical experiments concentrated on investigating whetherhaving less delay sensitive patients, as deﬁned in Condition 1, would lead to a larger optimalpanel size even under the M/D/1 setup. 19

Table 3: Selected comparison results between the M/M/1 and M/D/1 systems. The optimalpanel size is denoted by N2∗, and µ2∗ represents the optimal overbooking level. The resultsare derived by assuming κ = 1 and ξ = 0. Parameters N2∗(M/M/1) µ∗2(M/M/1) N2∗(M/D/1) µ∗2(M/D/1) (α, β) = (−5, 0.05) 2642 22.3 2709 22.4 (α, β) = (−3, 0.05) 2546 22.1 2630 22.2 (α, β) = (−1, 0.05) 2342 21.4 2449 21.5 (α, β) = (−1, 0.03) 2428 21.5 2516 21.6 (α, β) = (−1, 0.01) 2551 21.6 2608 21.7To populate our numerical experiments, we adopted the following parametric form forpatient show-up probabilities: 1 (11) pj = 1 + eα+βj ,where α and β are parameters and β > 0 so that pj decreases with j. One reason we chose thisparametric form was that it naturally arises if one uses logistic regression to estimate show-up probabilities as a function of patients’ appointment delay. The form is also compatiblewith Condition 1 in the sense that if we let pˆj = ,1 then Condition 1 holds when αˆ ≤ α 1+eαˆ+βˆjand βˆ ≤ β (see Lemma 6 in the Appendix). One implication of this in light of Propositions 2and 5 is that under our M/M/1 formulation any collective increase in the estimated show-upprobabilities would lead to a larger optimal panel size and a higher optimal overbooking levelregardless of which one of the two parameters the change is captured by.In the numerical experiments, we assumed that the regular daily capacity M = 20 and thedaily cost function ω(µ) = 0.2×[(µ−M )+]2. We varied the show-up probability parameters αand β, the delay threshold κ and the walk-in rate ξ. Speciﬁcally, we considered 36 diﬀerentcombinations of these four parameters by choosing them so that α ∈ {−5, −3, −1}, β ∈{0.01, 0.03, 0.05}, κ ∈ {0.5, 1}, and ξ ∈ {0, 0.5}. For each combination, we calculated theoptimal panel size and overbooking level under the assumption that the appointment queueoperates as an M/M/1 queue as well as the assumption that it operates as an M/D/1 queue.Table 3 provides the results for a selected subset of the 36 combinations.While not all the results are reported here, we ﬁnd that across all 36 combinations wetested, the average absolute percentage diﬀerence between the optimal panel size under the 20

M/M/1 setup and that under the M/D/1 setup is only 3.3%. That for the overbooking leveland the average net reward are only 0.23% and 2.98%, respectively. Furthermore, all the keystructural results obtained under the M/M/1 setup continue to hold under M/D/1 setup.In particular, for any ﬁxed combination of κ and ξ, the optimal panel size and overbookinglevel in both cases are decreasing in α for ﬁxed β and decreasing in β for ﬁxed α.4.2 Impact of customer cancellation and balkingOne simplifying assumption we made in our mathematical analysis was that patients neithercancel their appointments nor balk, i.e., choose not to join the appointment queue when theyﬁnd the appointment delay long. In this section, we investigate the eﬀect of this simpliﬁcationon our key ﬁndings via simulation. In our simulation model, we assumed that a patient who ﬁnds j scheduled appointmentsin the queue, independently of the others, would choose to join the appointment queue withprobability e−ηj, where η > 0 is the parameter for balking intensity. This probability modelcaptures the fact that patients are more likely not to schedule an appointment when theappointment queue/delay is longer. Note also that, a larger η indicates a higher likelihoodto balk for any given queue length j. To model cancellations, we assumed that each patient who joined the appointment queue,independently of the others and the system state, would choose to cancel her appointmentafter some random amount of time that has exponential distribution. However, cancelationonly occurs if the patient has not received service until then. In line with what mostlyhappens in practice, when an appointment is canceled, appointments that follow the can-celed appointment are not rescheduled to ﬁll in the newly vacated slot. Thus, the canceledappointment slot leaves a “hole” in the queue leaving other scheduled appointments intact.When a new appointment request arrives, rather than scheduling it at the end of the queue,one of these holes is ﬁlled if there are any. Speciﬁcally, the patient is scheduled for the slotthat is closest to service. (If the ﬁrst available slot happens to be the ﬁrst one in the queue,then the second hole in the queue is ﬁlled because the “service” for the ﬁrst slot has alreadystarted. This is to capture the fact that very late cancelations cannot be ﬁlled.) If thereare no holes in the queue, the appointment is scheduled at the end of the queue. As in theprevious section, patients who do not cancel their appointments, show up with probabilitiesthat follow the parametric form (11). 21

We considered three diﬀerent balking intensities η ∈ {0, 0.001, 0.003} and three diﬀerentcancelation rates θ ∈ {0.1, 0.2, 0.5}. For each combination of η and θ, we varied the show-upprobability parameters. In particular, we chose α ∈ {−5, −1} and β ∈ {0.01, 0.05}. In orderto get a better sense of what exactly these choices mean, consider a provider who sees 20patients per day. Then, when η = 0.001, for a patient who ﬁnds an appointment queue lengthof 2 days, 5 days, and 10 days at the time of her arrival, the balking probability is respectively4%, 10%, and 18%. When θ = 0.1, her cancelation probability before appointment isrespectively 18%, 39%, and 63%. Finally, when α = −5 and β = 0.01 her no-show probabilityis respectively 1%, 2%, and 5%. We assumed that the regular daily capacity M = 20, the daily cost function ω(µ) =0.2 × [(µ − M )+]2 and service times were deterministic. We also assumed there were no walk-in patients and there is no restriction on the expected delay, i.e., ξ = 0 and κ = ∞. Thus,in total, we considered 36 combinations for the choice of (η, θ, α, β). For each combination,we varied the panel size N with a step size of 10 and the daily service capacity level µ witha step size of 0.1, and ran simulation for each pair of (N, µ). We used the batch-meansmethod with a batch length of 3000 days and 11 batches, where the ﬁrst batch was used asthe warm-up period. We computed the average reward for each pair of (N, µ) and named thepair that gave the largest average reward the optimal solution. We summarize our results inTable 4, where Cases 1 through 4 correspond to four diﬀerent combinations of the show-upprobability parameters (α, β) = (−5, 0.01), (−5, 0.05), (−1, 0.01) and (−1, 0.05), respectively. One can observe from Table 4 that the higher the balking intensity, the larger the optimalpanel size. This is not surprising because balking makes the appointment queue lengths (andhence delays) shorter on average, which in turn means that patients are more likely to show-up giving the clinic an incentive to increase its panel size. The eﬀect of balking on theoverbooking level is more salient. We observe that, the optimal overbooking level does notappear to have a monotone relationship with the balking intensity, most likely due to thefact that the clinic has the ﬂexibility to choose the panel size as well. The clinic can managediﬀerent degrees of balking behavior by playing with the panel size appropriately but keepingthe overbooking level more or less constant. As in the case of balking, a higher cancelation rate leads to a larger optimal panel size(see Tables 3 and 4). However, the reader should note that in our simulation model, patientswho cancel their appointments do not reschedule, and thus cancellation has the eﬀect ofreducing the load on the clinic and thereby enabling it to handle a lager panel of patients. 22

Table 4: Optimal panel sizes and overbooking levels under cancelation. N ∗ denotes theoptimal panel size, and µ∗ represents the optimal overbooking level. The results are derivedby assuming κ = ∞ and ξ = 0.(N ∗, µ∗) Case 1 Case 2 Case 3 Case 4η=0 θ = 0.1 (3170, 22.5) (2990, 22.4) (2820, 21.8) (2550, 21.5) θ = 0.2 (3400, 22.6) (3230, 22.5) (2910, 21.5) (2660, 21.5) θ = 0.5 (3590, 22.4) (3590, 22.4) (3290, 21.7) (2890, 21.6) θ = 0.1 (3310, 22.6) (3080, 22.5) (2860, 21.8) (2580, 21.6)η = 0.001 θ = 0.2 (3510, 22.5) (3290, 22.5) (2970, 21.6) (2700, 21.5) θ = 0.5 (3820, 22.5) (3600, 22.5) (3300, 21.7) (2900, 21.5) θ = 0.1 (3390, 22.5) (3170, 22.5) (2940, 21.8) (2620, 21.4)η = 0.003 θ = 0.2 (3650, 22.5) (3360, 22.5) (3020, 21.9) (2710, 21.4) θ = 0.5 (3870, 22.5) (3680, 22.5) (3430, 21.8) (2920, 21.3)Thus, while our results suggest that with no or little rescheduling, the optimal panel sizeincreases with cancellation rate, it would be natural to expect that the same insight mightno longer hold when a high percentage of canceled appointments are rescheduled. Cases 1 through 4 can be seen as being ordered from being the least sensitive to incremen-tal delay to the most. From Lemma 6, we know that in Case 2 patients are more sensitivethan patients in Case 1 and patients in Case 4 are more sensitive than patients in Case 3.Cases 2 and 3 can actually not be ordered (Condition 1 does not hold either way) but wecan numerically verify that Case 2 patients are less sensitive to Case 3 patients at least whendelays are relatively short, speciﬁcally when there are fewer than 50 appointments in thequeue, which is the case a large proportion of the time under the optimal decisions. Lookingat Table 4, we can observe that the optimal panel size and the optimal overbooking level arelarger when the patients are less sensitive to appointment delays. Thus, our study suggeststhat our analytical results continue to hold even with patient cacellation and balking.4.3 Estimating the “optimal” panel size and comparison with Open AccessOur mathematical model is a stylized representation of an appointment queue and is notmeant to be used primarily as decision support tool to make precise decisions on the panelsize and overbooking level. Nevertheless, it is still of interest to investigate what the model 23

would suggest as the optimal panel size and how it would compare with panel sizes that arerecommended for Open Access implementation using data from an actual clinic. To that end, in this section, we estimate the “throughput maximizing” panel size usingour model and compare our numbers with those suggested by Green and Savin (2008) forOpen Access implementation. To make a proper comparison, we use exactly the same dataand the same no-show estimates used in Green and Savin (2008). Speciﬁcally, we let theindividual appointment demand rate λ0 to be 0.008 per day and the service rate to be 20customers per day, i.e., µ = 20. We use the following parametrical model for show-upprobabilities, pj, j ∈ Z: pj = 1 − (γmax − (γmax − γ0)e−⌊j/µ⌋/C )where γ0 is the minimum observed no-show rate, γmax is the maximum observed no-showrate, and C is the no-show backlog sensitivity parameter. Using data from a MagneticResonance Imaging (MRI) facility, Green and Savin (2008) estimated γ0, γmax, and C to be0.01, 0.31, and 50, respectively. Using these estimates, we ﬁnd that the optimal panel sizeunder the M/M/1 setup is 2459 while that under the M/D/1 setup is 2471. The M/M/1model estimate simply uses λ¯1 obtained through Proposition 1; the M/D/1 model estimateis obtained by numerically maximizing T (λ, 20) as deﬁned in (2) under the assumptions ofPoisson arrivals and deterministic service times with the queue length truncated at 1000. As we discussed before, the goal of Green and Savin (2008) is to estimate the ideal panelsize for Open Access, i.e., the panel size that will keep the clinic “in balance” for Open Accessimplementation. Using four diﬀerent models (M/D/1/K, M/M/1/K, and two simulationmodels) and four diﬀerent desired values for the same-day appointment probability, theyobtained 16 diﬀerent panel size estimates ranging from 2205 to 2368. Our throughput max-imizing panel size estimates are larger than what Green and Savin (2008) suggest for OpenAccess. This is not surprising mainly due to two reasons. First, having to provide same-dayservice forces the service provider to keep the panel sizes smaller. Second, our model as-sumes that no-show customers do not reschedule new appointments while Green and Savin(2008) assumed that all no-show customers immediately scheduled a new appointment. Sincerescheduling means more work load per customer, it leads to a smaller optimal panel size. One question of interest is the secondary eﬀects of using a throughput maximizing panelsize. The clinic might be maximizing throughput, but how about the eﬀect on the delaysthe patients experience? Do they wait for a long time, at least signiﬁcantly longer than they 24

Table 5: Computed values for the key performance measures under the M/M/1 model withno rescheduling. E(Q) is the average appointment queue length. E(W ) is the averagepatient appointment delay. PS is the probability that an arriving appointment request isaccommodated in the same day. PT is the probability that an arriving appointment requestis accommodated within the next two days.Panel Size Throughput E(Q) E(W ) PS PT2220 17.572 7.929 0.396 0.907 0.9912300 18.191 11.500 0.575 0.811 0.9642380 18.783 19.833 0.992 0.626 0.8602460 19.194 60.877 3.043 0.276 0.4762540 18.134 338.191 16.860 0.000 0.002would under the same-day scheduling policy? Table 5 clearly demonstrates the trade-oﬀamong system throughput, customer delays, and the fraction of customers who can bookappointments within a day or two. To be able to make a more meaningful comparison,following Green and Savin (2008), we truncate the queue length at 400 here, i.e., we assumean M/M/1/K queue with K = 400 instead of an M/M/1 queue. This does not aﬀect theresults in the ﬁrst four rows in the table signiﬁcantly; however, it is necessary for the lastrow since otherwise, the queue would have been unstable. In Table 5, the maximum throughput is 19.194 with a panel size of 2460. In this case,the average appointment delay is 3 days (since the daily service rate is 20 patients) andapproximately 28% of the patients can be seen on the day they call for an appointment. Theclinic can improve the waiting times and same-day access probabilities by reducing the panelsize. For example, if the panel size is 2220, approximately 90% of the customers can getsame-day appointments, but the throughput drops to about 17.572. This is more than an8% decrease, which suggests that committing to same-day appointments may not be optimalfrom a system eﬃciency point of view. If the clinic is interested in providing a high servicelevel and throughput is a secondary concern, then same-day appointment scheduling couldwork well. If eﬃciency is more important, it might pay oﬀ to be more ﬂexible. One can stillstick with Open Access but perhaps implement it a little less strictly by promising customersappointments within two or three days as opposed to the same day. 25

5 ConclusionThis paper uses stylized models to investigate the relationships between patients’ no-showbehavior and the optimal panel size and overbooking decisions. Our results provide insightsparticularly for clinics interested in reducing patient no-shows by behavioral interventionssuch as sending reminders for appointments. These interventions typically improve patientattendance but cannot eliminate no-shows completely. In general, clinics prefer higher show-up probabilities, which not only mean less time wasted and more patients served, but alsohelp clinics make better operational decisions because of the reduced uncertainty. Whatis far less clear is how clinics should alter their decisions in response to changes in patientshow-up probabilities. Our ﬁndings suggest that responses based on one’s intuition mightnot work as expected. For example, having patients who are more likely to show-up doesnot necessarily imply that the optimal panel size should be larger or smaller. What appearsto be more important is whether patients are more or less sensitive to additional delays.Past empirical studies on the eﬀectiveness of intervention policies have largely focused onchanges in no-show rates (Macharia et al. 1992, Guy et al. 2012), but did not investigate thechanges in the sensitivity of no-show probabilities to incremental changes in appointmentdelays. This is an important avenue for future research. The generic nature of our formulation allows us to generate insights without restrictingourselves to any speciﬁc appointment scheduling policy, and our main ﬁnding, which saysthat panel size decisions should be informed by the sensitivity of the show-up probabilitiesto incremental changes in appointment delays is likely to hold under more general conditionsand various appointment scheduling schemes. Nevertheless, our formulation is stylized andmore research is needed to provide support for this claim. It is also important to note thathow exactly one deﬁnes “sensitivity to incremental delays” may need to be reconsidered ifone uses a more detailed formulation of an appointment system. Our Condition 1 in thispaper, however, can help in identifying similar conditions in other formulations. Thus, oneavenue for future work is to model clinics that use standard appointment scheduling policiesin more detail (for example by explicitly considering day and time of the appointment,patient preferences etc.) and investigate the connection between optimal panel sizes andshow-up probabilities. Proving analytical results may not be possible, but investigation viaa simulation study would likely be fruitful. 26

ReferencesBean, A. G., J. Talaga. 1995. Predicting appointment breaking. Journal of Health Care Marketing 15(1) 29–34.Browder, A. 1996. Mathematical Analysis: An Introduction. Springer Verlag, New York, New York.Cayirli, T., E. Veral. 2003. Outpatient scheduling in health care: A review of literature. Production and Operations Management 12(4) 519–549.Daggy, J., M. Lawley, D. Willis, D. Thayer, C. Suelzer, P.C. DeLaurentis, A. Turkcan, S. Chakraborty, L. Sands. 2010. Using no-show modeling to improve clinic performance. Health Informatics Journal 16(4) 246–259.Dreiher, J., M. Froimovici, Y. Bibi, D.A. Vardy, A. Cicurel, A.D. Cohen. 2008. Nonatten- dance in obstetrics and gynecology patients. Gynecologic and Obstetric Investigation 66(1) 40–43.Fleck, E. 2012. Director, Internal Medicine, NewYork-Presbyterian Hospital/Ambulatory Care Network. Personal communication. July 19, 2012.Gallucci, G., W. Swartz, F. Hackerman. 2005. Brief reports: Impact of the wait for an initial appointment on the rate of kept appointments at a mental health center. Psychiatric Services 56(3) 344–346.Geraghty, M., F. Glynn, M. Amin, J. Kinsella. 2007. Patient mobile telephone text reminder: a novel way to reduce non-attendance at the ENT out-patient clinic. The Journal of Laryngology and Otology 122(3) 296–298.Green, L. V., S. Savin. 2008. Reducing delays for medical appointments: A queueing ap- proach. Operations Research 56(6) 1526–1538.Grunebaum, M., P. Luber, M. Callahan, A.C. Leon, M. Olfson, L. Portera. 1996. Predictors of missed appointments for psychiatric consultations in a primary care clinic. Psychiatric Services 47(8) 848–852.Gupta, D., B. Denton. 2008. Appointment scheduling in health care: Challenges and oppor- tunities. IIE Transactions 40(9) 800–819.Gupta, D., L. Wang. 2008. Revenue management for a primary-care clinic in the presence of patient choice. Operations Research 56(3) 576–592. 27

Gupta, D., W.Y. Wang. 2012. Patient appointments in ambulatory care. Randolph Hall, ed., Handbook of Healthcare System Scheduling, International Series in Operations Research and Management Science, vol. 168. Springer US, 65–104.Guy, R., J. Hocking, H. Wand, S. Stott, H. Ali, J. Kaldor. 2012. How eﬀective are short mes- sage service reminders at increasing clinic attendance? a meta-analysis and systematic review. Health Services Research 47(2) 614–632.Hashim, M. J. P. Franks, K. Fiscella. 2001. Eﬀectiveness of telephone reminders in improving rate of appointments kept at an outpatient clinic: a randomized controlled trial. The Journal of the American Board of Family Practice 14(3) 193–196.Jones, RB, AJ Hedley. 1988. Reducing non-attendance in an outpatient clinic. Public Health 102(4) 385–391.KC, Diwas, N. Osadchiy. 2012. Matching supply with demand in an outpatient clinic. Working Paper. Emory University, Goizueta Business School, Atlanta, GA.Kopach, R., P. C. DeLaurentis, M. Lawley, K. Muthuraman, L. Ozsen, R. Rardin, H. Wan, P. Intrevado, X. Qu, D. Willis. 2007. Eﬀects of clinical characteristics on successful open access scheduling. Health Care Management Science 10(2) 111–124.Kulkarni, V. G. 1995. Modeling and Analysis of Stochastic Systems. Chapman & Hall/CRC, Boca Raton, FL.LaGanga, L. R., S. R. Lawrence. 2007. Clinic overbooking to improve patient access and increase provider productivity. Decision Sciences 38(2) 251–276.Liu, N, S. Ziya, V. G. Kulkarni. 2010. Dynamic scheduling of outpatient appointments under patient no-shows and cancellations. Manufacturing & Service Operations Management 12(2) 347–364.Macharia, W. M., G. Leon, B. H. Rowe, B. J. Stephenson, R. B. Haynes. 1992. An overview of interventions to improve compliance with appointment keeping for medical services. The Journal of the American Medical Association 267(13) 1813–1817.Moore, C. G., P. Wilson-Witherspoon, J. C. Probst. 2001. Time and money: Eﬀects of no-showsat a family practice residency clinic. Family Medicine 33(7) 522–527.Norris, J.B., C. Kumar, S. Chand, H. Moskowitz, S.A. Shade, D.R. Willis. 2012. An empirical investigation into factors aﬀecting patient cancellations and no-shows at outpatient clinics. Decision Support Systems . 28

Patrick, J., M. L. Puterman, M. Queyranne. 2008. Dynamic multi-priority patient scheduling for a diagnostic resource. Operations Research 56(6) 1507–1525.Pesata, V., G. Pallija, A. A. Webb. 1999. A descriptive study of missed appointments: Families’ perceptions of barriers to care. Journal of Pediatric Health Care 13(4) 178– 182.Rosenthal, D. 2011. Director of Behavioral Science of Center for Family and Community Medicine at Columbia University. Personal communication. March 16, 2011.Schu¨tz, Hans-J¨org, Rainer Kolisch. 2012. Approximate dynamic programming for capacity allocation in the service industry. European Journal of Operational Research 218(1) 239–250.Shonick, W., B.W. Klein. 1977. An approach to reducing the adverse eﬀects of broken ap- pointments in primary care systems: development of a decision rule based on estimated conditional probabilities. Medical Care 15(5) 419–429.Ulmer, T., C. Troxler. 2004. The economic cost of missed appointments and the open access system. Community Health Scholars. University of Florida, Gainsville, FL.Wang, W.Y., D. Gupta. 2011. Adaptive appointment systems with patient preferences. Manufacturing & Service Operations Management 13(3) 373–389. 29

Online Supplement for “Panel Size and Overbooking Decisions for Appointment-based Services under Patient No-shows” Throughout the appendix, for a given function f (·), we use the notation f ′(·) and f ′′(·)to denote the ﬁrst and second derivatives of f (·) unless otherwise speciﬁed.Online Appendix - Proofs of the ResultsLemma 1 lim T (λ, µ) = lim[(1 − ξ)λ ∑∞ (1 − ρ)ρjpj + µξ] = µ[ξ + (1 − ξ)p∞]. λ→µ λ→µ j=0Proof of Lemma 1: ∑∞It suﬃces to show that limλ→µ λ j=0 (1 − ρ)ρj pj = µp∞, which is equivalent to show thatlimρ→1 µ ∑∞j=0(1 − proof, we only need to show that, ρ)ρj+1pj = µp∞. To further simplify the ∑∞ (1 − ρ)ρjpj = p∞, lim j=0 ρ→1since limρ→1 ρ = 1.Now, ﬁx an arbitrary ϵ > 0. Since {pj, j = 0, 1, 2, . . . } is a non-increasing sequence andlimj→∞ pj = p∞, there exists a positive integer K such that pj − p∞ < 1 ϵ for all j ≥ K + 1. 2Pick a ρ′ ∈ (0, 1) such that 1 − ρK+1 < 1 ϵ for all ρ ∈ [ρ′, 1). It then follows that, ∀ρ ∈ [ρ′, 1), 2 ∑∞ ∑∞ 0 ≤ | (1 − ρ)ρjpj − p∞| = (1 − ρ)ρj(pj − p∞) j=0 j=0 ∑K ∑∞ (1 − ρ)ρj(pj − p∞) = (1 − ρ)ρj(pj − p∞) + j=0 j=K+1 ∑K ∑∞ (1 − ρ)ρj(pK+1 − p∞) ≤ (1 − ρ)ρj + j=0 j=K+1 = (1 − ρK+1) + (pK+1 − p∞)ρK+1 11 < ϵ+ ϵ 22 = ϵ,which completes the proof. 1

Proof of Proposition 1:Consider ∑∞ ∑∞ T (λ, µ) = (1 − ξ)λ (1 − ρ)ρjpj + µξ = (1 − ξ)µ (ρj+1 − ρj+2)pj + µξ = µΛ(ρ), j=0 j=0where ρ = λ/µ and Λ(ρ) = (1 − ξ) ∑∞j=0(1 − ρ)ρj+1pj + ξ. Thus, for ﬁxed µ, maximizingT (λ, µ) with respect to λ is equivalent to maximizing Λ(ρ) with respect to ρ. Since ξ is aconstant and does not aﬀect the optimal value for ρ, we can assume ξ = 0 without loss ofgenerality. Then, we can write ∑∞ (12) Λ(ρ) = ρp0 + ρj+1(pj − pj−1). j=1Notice that Λ(ρ) is a power series of ρ and its radius of convergence, denoted by r, satisﬁesthe following condition (by Proposition 4.35 in Browder (1996)): 1/r = lim sup |pj − pj−1|1/j.Since |pj − pj−1| ≤ 1 for all j ≥ 1, we have r ≥ 1 and Λ(ρ) converges in [0, 1). Lemma 1implies that as ρ → 1, Λ(ρ) → p∞ and hence we deﬁne Λ(1) = p∞. It also follows fromTheorem 4.36 in Browder (1996) that Λ(ρ) is a function of class C∞ on (0, 1), implying thatits ﬁrst and second order derivatives exist in (0, 1). Then, for ρ ∈ (0, 1), we have ∑∞ (13) Λ′(ρ) = p0 + (j + 1)ρj(pj − pj−1), j=1and ∑∞ Λ′′(ρ) = j(j + 1)ρj−1(pj − pj−1), j=1Recall that pj ≥ pj+1 for all j and there exists a pair of j and k such that pj > pk for0 ≤ j < k. Thus, Λ′′(ρ) < 0 for ρ ∈ (0, 1) and Λ(ρ) is strictly concave in [0, 1]. SinceΛ′(0) = p0 > 0, we conclude that if there exists a τ ∈ (0, 1) such that Λ′(τ ) = 0, then τ isthe global optimizer to Λ(ρ) and λ¯1 = µτ ; otherwise, Λ(ρ) is strictly increasing in [0, 1] andhence the optimal value of ρ is 1 and λ¯1 = µ. Now, consider the optimal demand rate for Problem (P1) with a nontrivial constraintthat E(W ) ≤ κ < ∞. When µ is ﬁxed, E(W ) is strictly increasing in λ, and the constraintis binding when κµ2 λ = λb = κµ + . 1Since T (λ, µ) is a strictly concave function of λ as implied above, λ∗1 = min{λb, λ¯1}. 2

Proof of Proposition 2:We are comparing the optimal traﬃc intensities under {pj, j ≥ 0} and {pˆj, j ≥ 0}. Since ξdoes not aﬀect the choice of the optimal traﬃc intensities, we can assume ξ = 0 without lossof generality. Suppose that Condition 1 holds and let ∑∞ Λˆ (ρ) = (1 − ρ)ρj+1pˆj j=0and hence ∑∞ Λˆ ′(ρ) = pˆ0 + (j + 1)ρj(pˆj − pˆj−1). j=1Notice that Λ′(0) = p0 > 0 and Λˆ′(0) = pˆ0 > 0; and both Λ′(ρ) and Λˆ′(ρ) are strictlydecreasing in ρ. To show λˆ∗1 ≥ λ1∗, we only need to show λˆ1 ≥ λ¯1 where λ¯1 and λˆ1 arethe optimal arrival rates for Problem (P1) with κ = ∞ under show-up probabilities {pj}∞j=0and {pˆj}∞j=0, respectively. Thus, it suﬃces to show that, for 0 < ρ < 1, if Λ′(ρ) ≥ 0 thenΛˆ′(ρ) ≥ 0. We can rewrite Λ′(ρ) ≥ 0 as ∑∑j∞∞j==00((jj + 1)ρjpj ≥ ρ, + 2)ρjpjand Λˆ′(ρ) ≥ 0 in a similar form. Notice that the right hand sides of these two inequalitiesare both ρ; and that at ρ = 0, ∑∞ (j + 1)ρjpj = ∑∑∞jj∞==00((jj + 1)ρj pˆj = 1 > ρ. ∑j∞=0 (j + 2)ρjpj + 2)ρj pˆj 2 j=0Therefore, to show the desired result, it suﬃces to show that ∑∑∞j∞j==00((jj + 1)ρj pj − ∑∑jj∞∞==00((jj + 1)ρj pˆj ≤ 0, (14) + 2)ρj pj + 2)ρj pˆjfor 0 ≤ ρ < 1. We can rewrite (14) as ∑∞ ∑∞ ∑∞ ∑∞ (j + 1)ρjpj (k + 2)ρkpˆk − (j + 2)ρjpj (k + 1)ρkpˆk ≤ 0. (15) j=0 k=0 j=0 k=0 3

We can write the left hand side of the above inequality as ∑∞ ∑∞(j + 1)(k + 2)ρj+kpjpˆk − ∑∞ ∑∞ (j + 2)(k + 1)ρj+kpjpˆk j=0 k=0 j=0 k=0 ∑∞ ∑∞ = (j − k)ρj+kpjpˆk j=0 k=0 ∑∞ ∑∞ (j − k)ρj+kpjpˆk + ∑∞ ∑k−1 (j − k)ρj+kpjpˆk = k=0 j=k+1 k=0 j=0 ∑∞ ∑∞ ∑∞ ∑∞ = (j − k)ρj+kpjpˆk + (j − k)ρj+kpjpˆk k=0 j=k+1 j=0 k=j+1 ∑∞ ∑∞ ∑∞ ∑∞ = (j − k)ρj+kpjpˆk + (k − j)ρj+kpkpˆj k=0 j=k+1 k=0 j=k+1 ∑∞ ∑∞ = (j − k)ρj+k(pjpˆk − pkpˆj). k=0 j=k+1It is suﬃcient to show that pjpˆk ≤ pkpˆj for j > k. From Condition 1 we know that this holdsfor j = k + 1. Assume that the statement holds for j = k + s where s ∈ Z and s ≥ 1. Weneed to show that it also holds for j = k + s + 1. Notice that we have pk+spˆk ≤ pkpˆk+s (by induction argument) (16)and pk+s+1pˆk+s ≤ pk+spˆk+s+1 (by Condition 1). (17)We would like to show that pk+s+1pˆk ≤ pkpˆk+s+1. (18)If pk+s = 0, then pk+s+1 = 0 since pi is non-increasing in i, proving (18). Otherwise(pk+s > 0), if pˆk+s = 0 then in order for (16) to hold we must have pˆk = 0, again prov-ing (18). Otherwise (pk+s > 0 and pˆk+s > 0), then we can multiply (16) and (17) togetherand divide by the positive product pk+spˆk+s proving (18). This completes the proof.Lemma 2 If µ ≤ M , R(λ(µ), µ) is a linear and strictly increasing function of µ; otherwise,R(λ(µ), µ) is a strictly concave function of µ, and in particular, R′′(λ(µ), µ) = −ω′′(µ). 4

Proof of Lemma 2:By Proposition 1, we have that λ(µ) = ρ¯1µ, and thus T (λ(µ), µ) = µΛ(ρ¯1),where Λ(·) is as deﬁned in (8). It follows that { µΛ(ρ¯1) if µ ≤ M , µΛ(ρ¯1) − ω(µ) if µ > M .R(λ(µ), µ) =Since ω(µ) is twice diﬀerentiable on (M, ∞), the results follow.Proof of Proposition 3:Notice that ω(µ) = 0 if µ ≤ M . Thus Lemma 2 implies that µ¯2 ≥ M and we only need toconsider the following optimization problem:max R(λ(µ), µ) = mµ≥aMx{µΛ(ρ¯1) − ω(µ)}.µ≥MSince ω(µ) is continuous on [M, ∞), R(λ(µ), µ) is also continuous on [M, ∞). Also noticethat R(λ(µ), µ) is a strictly concave function for µ ≥ M since ω(µ) is strictly convex forµ ≥ M . Hence we do not need to consider the boundary point µ = M separately. ConsiderR+(λ(µ), µ) = Λ(ρ¯1) − ω+(µ) for µ ≥ M ,where R+ represent the right derivative of R(λ(µ), µ) with respect to µ. Notice thatR+(λ(µ), µ) is a strictly decreasing function of µ due to strict convexity of ω(µ) on [M, ∞).We conclude that if ω+(M ) ≥ Λ(ρ¯1), then µ¯2 = M ; if limµ→∞ ω+(µ) ≤ Λ(ρ¯1), then µ¯2 = ∞;otherwise, µ¯2 solves the following equation,R+(λ(µ), µ) = Λ(ρ¯1) − ω+(µ) = 0. (19)Since ω(·) is strictly convex on [M, ∞) and twice diﬀerentiable on (M, ∞), we know thatω+(µ) is a continuous and strictly increasing function on [M, ∞), and hence its inversefunction (ω+)−1(·) exists on the domain Y = {ω+(µ), µ ≥ M }. From (19), we obtain µ¯2 = (ω+)−1(Λ(ρ¯1)).The uniqueness of µ¯2 and λ¯2 comes from the strict convexity of R(λ(µ), µ) when µ ≥ M(shown in Lemma 2) and Proposition 1, respectively. 5

Proof of Corollary 1:Suppose that there exists a ﬁnite µ, denoted as µ¯, such that ω+(µ¯) > 1. From the assump-tions on ω(·), we have µ¯ ≥ M . We will show that the optimal solution for the followingproblem is the same as that of Problem (P2): maxµ,λ:0≤λ≤µ R(λ, µ) (P3) s.t. E(W ) ≤ κ µ ≤ µ¯.Assume otherwise for an contradiction. Let X2 and X3 represent the feasible regions ofProblem (P2) and (P3), respectively. Suppose that there exists (λ∗2, µ∗2) such that λ∗2, µ∗2) ∈X2, µ2∗ > µ¯ and R(λ2∗, µ∗2) > R(λ, µ) for all (λ, µ) ∈ X3. Notice that the service levelconstraint can be rewritten as follows. λ ≤ µ(1 − 1 ). κµ + 1Consider two cases. Case (1): the service level constraint is not binding at (λ∗2, µ∗2), i.e., λ2∗ < µ∗2(1 − 1 ). κµ2∗ + 1Let ρ2∗ = λ2∗/µ2∗. Since the constraint above is not binding, we can identify a pair of (λ2∗, µ2∗)such that ρ2∗ = λ2∗/µ∗2 and µ2∗ < µ∗2. We can choose µ∗2 close enough to µ2∗ such that µ2∗ > µ¯.It follows thatR(λ∗2, µ2∗) = µ2∗Λ(ρ∗2) − ω(µ2∗) < µ∗2Λ(ρ2∗) − ω(µ2∗) = R(λ2∗, µ∗2),since ω+(µ∗2) ≥ ω+(µ2∗) > 1 ≥ Λ(ρ2∗). This contradicts the optimality of (λ∗2, µ∗2). Case (2): the service level constraint is binding at (λ2∗, µ∗2), i.e., λ∗2 = µ2∗(1 − 1 ). κµ2∗ + 1We will show that there exist other solutions that make the service level constraint bindingbut at the same time achieve a strictly larger objective value. It can be shown that whenthe above equality holds, the objective function can be expressed in terms of µ alone as inthe following: 1 ∑∞ 1 1 j κµ + ( κµ +Rb(µ) = (1 − ξ)µ(1 − ) κµ + )(1 − ) pj + µξ − ω(µ). 1 1 1 j=0 6

First notice that 1 ∑∞ 1 1 j κµ + ( κµ + Rb(µ) = (1 − ξ)µ(1 − ) κµ + )(1 − ) pj + µξ − ω(µ) 1 1 1 j=0 1 κ2µ2 ∑∞ 1 1 j ξ) κµ + 1 ( κµ + = (1 − κµ + )(1 − ) pj + µξ − ω(µ) κ 1 1 j=0 − 1 ∑∞ κµ j+2 − ξ) ( = (1 κµ + ) pj + µξ ω(µ). (20) κ 1 j=0For µ > M, ω+(µ) = ω′(µ) = dω(µ) . Thus, dµ dRb(µ) = (1 − ξ) ∑∞ + κµ j+1 (κµ 1 1)2 pj + ξ − ω′(µ) dµ (j 2)( + ) j=0 κµ + 1 ≤ ∑∞ κµ j+1 1 + ξ − ω′(µ) (1 − ξ) (j + 2)( ) κµ + 1 (κµ + 1)2 j=0 = (1 − κ2µ2 + 2κµ + ξ − ω′(µ) ξ) + 1)2 (κµ ≤ 1 − ω′(µ).Now, since ω′(µ2∗) ≥ ω+(µ¯) > 1, there exists ε > 0 such that Rb(µ∗2 − ε) > Rb(µ∗2). This is acontradiction to the optimality of (λ2∗, µ2∗). Thus we have proved the equivalence of Problem (P3) and (P2). Now, since R(λ, µ) iscontinuous and the feasible region of Problem (P3) is closed and bounded (i.e., compact), itfollows that there exists a ﬁnite optimal solution for this problem (Corollary 6.57 in Browder1996). This completes the proof.Proof of Proposition 4:To see the ﬁrst part of the proposition, ﬁrst note that the constraint on the expected servicetime can equivalently be written as λ ≤ κµ = 1 − 1 µ κµ + 1 . κµ + 1Then, since γ < µ¯2, we have λ¯2 = ρ¯1 = 1− 1 ≤ 1− 1 (21) µ¯2 κγ + 1 , κµ¯2 + 1and therefore (λ¯2, µ¯2) satisﬁes the waiting time constraint and is the optimal solution to theconstrained problem as well. Consequently, we have λ2∗ = λ¯2. 7

Now, let { R(λ, µ) if the waiting time constraint is satisﬁed, −∞ otherwise. Rc(λ, µ) =If γ = ∞, it is obvious that µ2∗ ≤ γ. Consider the case where γ < ∞. To prove that µ2∗ ≤ γif µ¯2 ≤ γ, it suﬃces to show that for any µ > γ and λ ≥ 0, Rc(ρ¯1γ, γ) > Rc(λ, µ).Fix µ > γ and λ > 0. Then, µ > γ ≥ µ¯2 ≥ M, (22)andRc(λ, µ) ≤ max R(x, µ) (recall that λ and µ are ﬁxed) x≥0 = R(ρ¯1µ, µ) (by Proposition 1) < R(ρ¯1γ, γ) (by the strict concavity of R(ρ¯1y, y) in y when y ≥ M and (22)) = Rc(ρ¯1γ, γ).The last equality is due to the fact that when µ = γ and λ = ρ¯1γ, the waiting time constraintis satisﬁed. Now it is left to show that at optimality, the waiting time constraint is binding.This can be proved by constructing a contradiction. Suppose that the constraint is notbinding, then λ∗2 < µ∗2(1 − 1 ) ≤ µ2∗(1 − 1 ) = µ2∗ρ¯1, κµ2∗ + 1 κγ + 1since µ∗2 ≤ γ. Notice that for ﬁxed µ = µ∗2, R(λ, µ) is strictly concave in λ and is strictlyincreasing in λ when λ ≤ ρ¯1µ. Therefore,Rc(µ∗2(1 − 1 ), µ2∗) = R(µ2∗(1 − 1 ), µ∗2) > R(λ∗2, µ∗2) = Rc(λ∗2, µ2∗), κµ2∗ + 1 κµ∗2 + 1which is a contradiction to the optimality of (λ∗2, µ∗2). This completes the proof.Lemma 3 Let λˆ2 and µˆ2 denote the optimal arrival rate and service rate in the unconstrainedproblem under the show-up probability vector pˆ = {pˆj}. If pˆj ≥ pj for all j, then µˆ2 ≥ µ¯2. Ifpˆj ≥ pj and pˆj+1pj ≥ pˆjpj+1 for all j, then µˆ2 ≥ µ¯2 and λˆ2 ≥ λ¯2. 8

Proof of Lemma 3:Let ρˆ1 be the optimal traﬃc intensity in Problem (P1) with κ = ∞ when the show-upprobability vector is pˆ = {pˆj}. To prove µˆ2 ≥ µ¯2, it suﬃces to show that Λˆ(ρˆ1) ≥ Λ(ρ¯1),where ∑∞ Λˆ(ρ) = (1 − ξ) (1 − ρ)ρj+1pˆj + ξ. (23) j=0From the proof of Proposition 1 we know that, Λ(ρ¯1) = max Λ(ρ), 0≤ρ≤1and Λˆ (ρˆ1) = max Λˆ (ρ).Since pˆj ≥ pj for all j, we have 0≤ρ≤1 Λˆ (ρˆ1) = max Λˆ (ρ) ≥ max Λ(ρ) = Λ(ρ¯1). 0≤ρ≤1 0≤ρ≤1Therefore, µˆ2 ≥ µ¯2. From the proof of Proposition 2, if pˆj+1pj ≥ pˆjpj+1 ∀j,then ρˆ1 ≥ ρ¯1, and hence λˆ2 = µˆ2ρˆ1 ≥ µ¯2ρ¯1 = λ¯2.Lemma 4 Let µˆb∗ be the smallest maximizer to the following problem Rˆb(µ) 1 ∑∞ 1 1 j κµ + ( κµ +max = (1 − ξ)µ(1 − ) κµ + )(1 − ) pˆj + µξ − ω(µ), (24) 1 1 1 µ≥0 j=0which is the same as problem (9) with pj replaced by pˆj. If pˆj ≥ pj for all j, then µˆb∗ ≥ µ∗b,where µ∗b is the smallest maximizer to problem (9).Proof of Lemma 4:It suﬃces to show that Rˆb+(µ) ≥ Rb+(µ), ∀µ > 0,where f + represent the right derivative of function f . First notice that Rb(µ) can be simpli-ﬁed as in (20): − 1 ∑∞ κµ j+2 − ξ) ( Rb(µ) = (1 κµ + ) pj + µξ ω(µ). k 1 j=0 9

Thus, ∑∞ (j Rb+(µ) = (1 − ξ) + κµ j+1 (κµ 1 1)2 pj + ξ − ω+(µ). 2)( + j=0 ) κµ + 1Then the result immediately follows.Lemma 5 If µ¯2 ≥ γ, then µ∗b ≤ µ¯2.Proof of Lemma 5:Fix an arbitrary µ > µ¯2 ≥ M . It suﬃces to show that Rb(µ¯2) > Rb(µ), where Rb(µ) is asdeﬁned in (10). Let ρµ¯2 = 1 − 1 ,and 1 κµ¯2 + ρµ = 1 − 1 . 1 κµ +Let f (x, r) = rx − ω(x) where r ≥ 0. We claim that Rb(µ¯2) = f (µ¯2, Λ(ρµ¯2)) ≥ f (µ, Λ(ρµ¯2)) > f (µ, Λ(ρµ)) = Rb(µ).The ﬁrst and the last equality follow by deﬁnition. To show the ﬁrst inequality, ﬁrst noticethat f (x, r) is a strictly concave function of x for ﬁxed r when x ≥ M . Let f +(x, r)denote the right derivative of f (x, r) with respect to x for a ﬁxed r. It suﬃces to show thatf +(µ¯2, Λ(ρµ¯2)) ≤ 0, which follows fromf +(µ¯2, Λ(ρµ¯2)) = Λ(ρµ¯2) − ω+(µ¯2) ≤ Λ(ρµ¯2) − Λ(ρ¯1) (by Proposition 3 and the fact that µ¯2 < ∞) ≤ 0. (by the fact that Λ(ρ¯1) = max Λ(ρ)) 0≤ρ≤1 To show the second inequality, it suﬃces to show that Λ(ρµ¯2) > Λ(ρµ). Notice that Λ(ρ)is strictly concave in ρ and maximized at ρ¯1. Since µ > µ¯2 ≥ γ, it follows that ρµ > ρµ¯2 ≥ ρ¯1,and hence Λ(ρµ) < Λ(ρµ¯2) ≤ Λ(ρ¯1), which completes the proof.Proof of Proposition 5:Let γˆ be such that the following holds: ρˆ1 = 1 − 1 . κγˆ + 1 10

If pˆj+1pj ≥ pˆjpj+1 for all j, then it follows from Proposition 2 that ρˆ1 ≥ ρ¯1 and hence γˆ ≥ γ. (25)We consider the following four cases:Case (i): γ > µ¯2 and γˆ ≤ µˆ2.From Proposition 4, we have µ2∗ = µ∗b and µˆ2∗ = µˆ2. Then, using Lemmas 4, 5 and the factthat pˆj ≥ pj for all j, we can conclude that µ∗b ≤ µˆ∗b and µˆb∗ ≤ µˆ2. It then follows thatµˆ2∗ ≥ µ2∗. If we also have pˆj+1pj ≥ pˆjpj+1 for all j, then by Proposition 4 and (25), we knowthat µ∗2 ≤ γ ≤ γˆ ≤ µˆ2 = µˆ2∗, and henceλˆ∗2 = µˆ∗2ρˆ1 = µˆ2∗(1 − 1 ) ≥ µ2∗(1 − 1 ) = λ2∗. κγˆ + 1 κµ2∗ + 1Case (ii): γ > µ¯2 and γˆ > µˆ2.From Proposition 4, we know that µˆ∗2 = µˆb∗ and µ2∗ = µb∗. It follows from Lemma 4 andpˆj ≥ pj that µˆ2∗ = µˆ∗b ≥ µb∗ = µ∗2, and by Proposition 4, we have λˆ∗2 = µˆ∗2(1 − 1 ) ≥ µ2∗(1 − 1 ) = λ∗2. κµˆ∗2 + 1 κµ2∗ + 1Case (iii): γ ≤ µ¯2 and γˆ ≤ µˆ2.From Proposition 4 and Lemma 3, we have µ∗2 = µ¯2 ≤ µˆ2 = µˆ∗2 if pˆj ≥ pj for all j; andλ2∗ = λ¯2 ≤ λˆ2 = λˆ2∗ if pˆj ≥ pj and pˆj+1pj ≥ pˆjpj+1 for all j.Case (iv): γ ≤ µ¯2 and γˆ > µˆ2.First consider the situation when γ = µ¯2 and γˆ > µˆ2. In this case, µ¯2 = µ∗2 = µ∗b = γ, i.e.,the solution to the unconstrained problem is the same as the solution to the constrainedproblem under the show-up probability vector p. By Proposition 4, we know that µˆb∗ = µˆ∗2.The proof then follows as in Case (ii). Now, suppose that γ < µ¯2 and γˆ > µˆ2. We claim that (A) if pˆj ≥ pj for all j, then thereexists a show-up probability vector p˜ = {p˜j}j∞=0 such that p˜ satisﬁes the same assumptionsthe sequence p = {pj} does (i.e., decreasing in j and there exists some j < k such thatp˜j > p˜k), pˆj ≥ p˜j ≥ pj for all j and γ˜ = µ˜2, where γ˜ satisﬁes the following equation ρ˜1 = 1 − 1 . (26) κγ˜ + 1Note that µ˜2 is the optimal service rate for the unconstrained problem under show-up prob-ability vector p˜ = {p˜j} and ρ˜1 is the optimal traﬃc intensity deﬁned in Proposition 1 by 11

using p˜j instead of pj; and (B) the vector p˜ = {p˜j} also has the following property: ifpˆj+1pj ≥ pj+1pˆj, then pˆj+1p˜j ≥ p˜j+1pˆj and p˜j+1pj ≥ pj+1p˜j, i.e., it preserves the order ofsensitivity to delay. These two claims (A and B) will be shown at the end of this proof. Now, given that Claim A holds, if pˆj ≥ pj, then pˆj ≥ p˜j ≥ pj and γ˜ = µ˜2. It follows fromLemma 3 that µˆ2 ≥ µ˜2 ≥ µ¯2. Since γ˜ = µ˜2, γ < µ¯2 and γˆ > µˆ2, we also have γˆ ≥ γ˜ ≥ γ.Given γ ≤ µ¯2 and γ˜ ≤ µ˜2, we conclude, following as in the proof of Case (iii), that µ∗2 ≤ µ˜2∗.Since γ˜ = µ˜2 and γˆ > µˆ2, we obtain, from the ﬁrst part of analysis in case (iv), that µ˜∗2 ≤ µˆ∗2.Combining the results together, we conclude that µˆ2∗ ≥ µ2∗ if pˆj ≥ pj for all j. If we further assume pˆj+1pj ≥ pj+1pˆj, then by claim B, we have pˆj+1p˜j ≥ p˜j+1pˆj andp˜j+1pj ≥ pj+1p˜j. Given γ ≤ µ¯2 and γ˜ ≤ µ˜2, we conclude, by using results obtained in case(iii), that λ∗2 ≤ λ˜∗2. Since γ˜ = µ˜2 and γˆ > µˆ2, we can use the the ﬁrst part of analysis incase (iv) to conclude that λ˜2∗ ≤ λˆ∗2. Combining the results together, we have that λˆ∗2 ≥ λ2∗ ifpˆj ≥ pj and pˆj+1pj ≥ pj+1pˆj for all j.Proof of Claims A and B: We will prove claim A by showing that if pˆj ≥ pj, then thereexists a β ∈ [0, 1] such that p˜j = (1 − β)pj + βpˆj, pˆj ≥ p˜j ≥ pj and γ˜ = µ˜2. First, it isobvious that ∀β ∈ [0, 1], pˆj ≥ p˜j ≥ pj since p˜j is a convex combination of pj and pˆj. It isalso easy to see that p˜ carries the properties assumed for p = {pj} (i.e., decreasing in j andthere exist some j < k such that p˜j > p˜k). Next, we will show that there exists a β ∈ [0, 1] such that γ˜ = µ˜2. Since γ < ∞, we knowthat ρ¯1 < 1. Consider two cases. Case (1): if γˆ = ∞, this implies that ρˆ1 = 1. For any ρ ∈ [ρ¯1, 1), Proposition 1 impliesthat Λ′(ρ) ≤ 0 and Λˆ′(ρ) ≥ 0. Thus there exists a β ∈ [0, 1] such that βΛ′(ρ)+(1−β)Λˆ′(ρ) = 0where Λ(ρ) and Λˆ(ρ) are deﬁned in (12) and (23), respectively; in other words, there exista β and its corresponding p˜ such that ρ˜1 = ρ ∈ [ρ¯1, 1) where ρ˜1 denotes the optimal traﬃcintensity under p˜. For such a β, ρ˜1 is unique (by Proposition 1) and hence can be regardedas a function of β. Consider the set Θ = {β : 0 ≤ β ≤ 1, ρ˜1(β) ∈ [ρ¯1, 1)}. By ImplicitFunction Theorem, one can show that ρ˜1 is a continuous function of β in Θ. Claim B (whichwill be shown shortly) and Proposition 2 imply that ρ˜1 increases in β ∈ [0, 1]. Recall thatfor all ρ ∈ [ρ¯1, 1), there is a β such that ρ˜1 = ρ. Since ρ˜1 ≤ 1, we know when sup Θ ≤ β ≤ 1,ρ˜1 = 1, and as β approaches sup Θ from the left, ρ˜1 approaches 1 because it is a continuousand increasing function of β. Thus the left and right limits of ρ˜1 are the same at β = sup Θ.This concludes that ρ˜1 is continuous for β ∈ [0, 1]. Case (2): if γˆ < ∞, this implies that ρˆ1 < 1. Following a similar proof in Case (1) we 12

can show that ρ˜1 is continuous for β ∈ [0, 1]. It then follows that γ˜ is also a continuous function of β (see (26)). Deﬁne Λ˜(ρ) as Λ(ρ)by replacing pj’s with p˜j’s. Notice that Λ˜(ρ˜1) is also a continuous function of β since everycomponent of it is continuous in β. Proposition 3 implies that µ˜2 is a continuous functionof Λ˜(ρ˜1) (and hence β). Thus, both γ˜ and µ˜2 are continuous functions of β. When β = 0,i.e., p˜j = pj, γ˜ = γ < µ¯2 = µ˜2; and when β = 1, i.e., p˜j = pˆj, γ˜ = γˆ > µˆ2 = µ˜2. Therefore,there must exist a β ∈ [0, 1] such that γ˜ = µ˜2. It is left to show Claim B that if pˆj+1pj ≥ pj+1pˆj, then pˆj+1p˜j ≥ p˜j+1pˆj and p˜j+1pj ≥pj+1p˜j. Consider an arbitrary β ∈ [0, 1] and notice thatpˆj+1p˜j −p˜j+1pˆj = pˆj+1[(1−β)pj +βpˆj]−[(1−β)pj+1 +βpˆj+1]pˆj = (1−β)(pˆj+1pj −pj+1pˆj) ≥ 0,which shows the ﬁrst inequality. The second inequality follows using similar arguments. Thiscompletes the proof of the proposition.Proof of Proposition 6:When κ is large enough, i.e., κ > ,ρ¯1 the optimal solution to the constrained problem is (1−ρ¯1)µ¯2the same as the optimal solution to the unconstrained problem and ρ∗2 = .λ¯2 If κ ≤ ,ρ¯1 µ¯2 (1−ρ¯1)µ¯2then the constraint is always binding and the problem reduces to (9). We ﬁrst rewrite (10)as follows ∑∞ Rb(ρ) = (1 − 1 ρj+2pj + ξ (1 ρ − ω( ρ ξ) − ρ)κ (1 − ρ)κ), j=0 κwhere ρ= λ =1− 1 . µ κµ + 1Denote the smallest optimal maximizer of the above function as ρ∗b, and notice that ρb∗ = ρ2∗if κ ≤ .ρ¯1 Therefore, it suﬃces to show that ρb∗ increases in κ. (1−ρ¯1)µ¯2 For ease of presentation, we write ρb∗ = ρ∗b(κ). Take arbitrary 0 ≤ κ1 ≤ κ2. We will showthat ρb∗(κ1) ≤ ρ∗b(κ2). Consider the following problem for some α > 0. max (1 − 1 ∑∞ ρj+2pj + ξ (1 ρ − αω( (1 − ρ ). (27) ξ) − ρ)κ1 ρ)ακ1 ρ≥0 j=0 κ1It is clear that ρ∗b(κ1) is the maximizer to problem (27) with α = 1. We claim that ρb∗(κ2)is the maximizer to problem (27) with α = κ2 ≥ 1, which will be proved at the end. Thus, κ1 13

to show that ρb∗(κ1) ≤ ρb∗(κ2), it suﬃces to prove that the maximizer to the problem (27)increases in α. Let R˜b(α, ρ) = (1 − 1 ∑∞ + ξ ρ − αω( ρ ξ) ρj+2pj (1 − ρ)κ1 (1 ). κ1 j=0 − ρ)ακ1It is then suﬃcient to show that R˜b(α, ρ) is supermodular. Notice that∂R˜b(α, ρ) = (1 − 1 ∑∞ + 2)ρj+1pj + ξ 1 − αω′( ρ1 (1 1 ∂ρ ξ) (j (1 − ρ)2κ1 (1 − ρ)ακ1 ) ακ1 − ρ)2 κ1 j=0 = (1 − 1 ∑∞ + 2)ρj+1pj + ξ 1 − ω′( ρ1 (1 1 ξ) (j (1 − ρ)2κ1 (1 − ρ)ακ1 ) κ1 − ρ)2 , κ1 j=0and thus ∂2R˜b(α, ρ) = −ω′′( (1 − ρ ) 1 (1 1 ρ)2 (1 ρ (− 1 ) ∂ρ∂α ρ)ακ1 κ1 − − ρ)κ1 α2 = ω′′( ρ1 ρ ≥ 0 (by the convexity of ω), (1 − ρ)ακ1 ) κ12α2 (1 − ρ)3where ω′ and ω′′ represent the ﬁrst and the second right derivatives of ω. Now, it is left to show the claim made above that ρb∗(κ2) is the maximizer to problem(27) with α = κ2 ≥ 1. To show that, ﬁrst notice that for κ = κ2, κ1 Rb(ρ) = (1 − 1 ∑∞ + ξ ρ − ω( ρ ξ) ρj+2pj (1 − ρ)κ2 (1 − ρ)κ2 ) κ2 j=0 = κ1 [(1 − 1 ∑∞ + ξ ρ − κ2 ω( ρ κ1 )] κ2 ξ) ρj+2pj (1 − ρ)κ1 κ1 (1 − ρ)κ1 κ2 κ1 j=0 = 1 − 1 ∑∞ + ξ ρ − αω( ρ [(1 ξ) ρj+2pj (1 − ρ)κ1 (1 )], α κ1 j=0 − ρ)ακ1where α = κ2 ≥ 1. To maximize the above equation with respect to ρ for ﬁxed κ2, the ﬁrst κ1term 1 is irrelevant and can be ignored for optimization. Therefore ρ∗b (κ2) is the maximizer αto the following problem for α = κ2 ≥ 1: κ1 max (1 − 1 ∑∞ ρj+2pj + ξ (1 ρ ρ ξ) − ρ)κ1 − αω( (1 − ρ)ακ1 ), ρ≥0 j=0 κ1which is problem (27). This completes the proof. . 14

Proof of Proposition 7:The case when κ = ∞ is evident as ρ¯1 does not change with ξ and thus Λ(ρ¯1) as a functionof ξ increases in ξ. It follows from Proposition 3 that the optimal service rate µ¯2 increasesin ξ. Since ρ¯1 is independent of ξ, the optimal arrival rate λ¯2 = ρ¯1µ¯2 increases with ξ. Now, consider the case when κ < ∞, and write λ∗2 = λ2∗(ξ), µ∗2 = µ∗2(ξ), ρ∗2 = ρ2∗(ξ),λ¯2 = λ¯2(ξ) and µ¯2 = µ¯2(ξ) to explicitly express their dependence on ξ. Take arbitrary ξ1and ξ2 such that 0 ≤ ξ1 ≤ ξ2 ≤ 1 and ﬁx all other parameters in the model. We examinethe following three cases. Case 1: if (λ2∗(ξ1), µ2∗(ξ1)) = (λ¯2(ξ1), µ¯2(ξ1)), then λ¯2(ξ1) λ¯2(ξ1)) = ρ¯1 ≤ κ. (28) µ¯2(ξ1)(µ¯2(ξ1) − µ¯2(ξ1)(1 − ρ¯1)Since ξ2 ≥ ξ1, we have µ¯2(ξ2) ≥ µ¯2(ξ1). Noting λ¯2(ξ2) = ρ¯1µ¯2(ξ2), it follows from (28) that(λ¯2(ξ2), µ¯2(ξ2)) also satisﬁes the wait time constraint and thus (λ∗2(ξ2), µ∗2(ξ2)) = (λ¯2(ξ2), µ¯2(ξ2)),completing the proof of this case.Case 2: if (λ∗2(ξ1), µ∗2(ξ1)) ̸= (λ¯2(ξ1), µ¯2(ξ1)) and (λ∗2(ξ2), µ∗2(ξ2)) ≠ (λ¯2(ξ2), µ¯2(ξ2)). Thismeans that both the optimal solutions when ξ = ξ1 and ξ = ξ2 occur when the wait timeconstraint is binding. To show µ∗2(ξ2) ≥ µ∗2(ξ1), it suﬃces to show that dRb(µ) ≥ 0, where dµdξRb(µ) is deﬁned in (20). This can be shown as follows dRb(µ) = − ∑∞ + κµ j+1 (κµ 1 1)2 pj + 1 dµdξ (j 2)( + ) j=0 κµ + 1 ≥ ∑∞ + κµ j+1 1 1)2 + 1 − (j 2)( + ) j=0 κµ + 1 (κµ κ2µ2 + 2κµ = − (κµ + 1)2 + 1 ≥ 0.Since the expected waiting time constraint is binding, we have ρ2∗(ξ) = κµ∗2(ξ) , κµ∗2(ξ) + 1which is increasing in µ∗2(ξ). Hence λ2∗(ξ) increases in ξ, completing the proof of this case.Case 3: if (λ2∗(ξ1), µ∗2(ξ1)) ≠ (λ¯2(ξ1), µ¯2(ξ1)) and (λ2∗(ξ2), µ2∗(ξ2)) = (λ¯2(ξ2), µ¯2(ξ2)), thenwe claim that there exists a ξ˜ ∈ [ξ1, ξ2] such that the optimal solutions with the expectedwaiting time constraint coincide with those without. That is, λ¯2(ξ˜) = λ∗2(ξ˜), µ¯2(ξ˜) = µ2∗(ξ˜),and λ¯2(ξ˜) = κ. Then we have ρ2∗(ξ1) ≤ ρ∗2(ξ˜) ≤ ρ2∗(ξ2) where the ﬁrst inequality µ¯2(ξ˜)(µ¯2(ξ˜)−λ¯2(ξ˜)) 15

follows from a similar proof of Case (2) above and the second inequality follows from Case(1). Similar ordering also holds for the optimal demand rate and overbooking level. Tocomplete the proof of this case, we only need to show the existence of ξ˜. First note that(λ2∗(ξ2), µ2∗(ξ2)) = (λ¯2(ξ2), µ¯2(ξ2)) implies that the expected waiting time is no larger than κat (λ¯2(ξ2), µ¯2(ξ2)). Let ξ = ξ2 − ϵ where 0 ≤ ϵ ≤ ξ2 − ξ1. When ϵ is suﬃciently small, theexpected waiting time is no larger than κ at (λ¯2(ξ), µ¯2(ξ)) because the expected waiting timeis a continuous decreasing function of ξ. (To see this continuity and monotonicity, recall thatρ¯1 does not depend on ξ; and Proposition 3 implies that µ¯2(ξ) is continuously increasing inξ.) Increasing ϵ we decrease ξ and increase the expected wait time at (λ¯2(ξ), µ¯2(ξ)), andwe will eventually arrive at some ξ ∈ [ξ1, ξ2] where the expected wait time is exactly κ forλ¯2(ξ) and µ¯2(ξ). This ξ is the ξ˜ we are searching for. If we cannot ﬁnd such ξ, then itimplies that the expected wait time is no larger than κ at (λ¯2(ξ), µ¯2(ξ)), ∀ξ ∈ [ξ1, ξ2]. Thus,(λ¯2(ξ1), µ¯2(ξ1)) should be optimal for P2, leading to a contradiction with the assumption forthis case (that (λ∗2(ξ1), µ2∗(ξ1)) ̸= (λ¯2(ξ1), µ¯2(ξ1))). This completes the proof of the result. .Lemma 6 If pj takes the form (11), then for j = 0, 1, 2, . . . , pj+1 is decreasing in α and β, pjrespectively, given that the other parameter is ﬁxed.Proof of Lemma 6:Let r denote the ratio between pj+1 and pj, i.e., r = pj+1 = 1 + eα+βj pj 1 + eα+β(j+1) .It follows that ∂r = (1 + 1 [eα+βj (1 + eα+β(j+1)) − (1 + eα+βj )eα+β(j+1)] ∂α eα+β(j+1))2 = eα+βj (1 − eβ) < 0; (1 + eα+β(j+1))2and ∂r = (1 + 1 [j eα+βj (1 + eα+β(j+1)) − (1 + eα+βj )(j + 1)eα+β(j+1)] ∂β eα+β(j+1))2 = (1 + 1 (j eα+βj − (j + 1)eα+β(j+1) − e2α+2βj+1) < 0. eα+β(j+1))2. 16

# Panel Size and Overbooking Decisions for Appointment-based ...

##
**Description: ** Panel Size and Overbooking Decisions for Appointment-based Services under Patient No-shows Nan Liu • Serhan Ziya Department of Health Policy and Management, Mailman ...

### Read the Text Version

No Text Content!

- 1 - 46

Pages: