Introduction

Appointment systems are wildly used is people's daily life. They are used in the scenario that people's demand can be known in advance, for example, hospitals, barbershops, and government departments. Appointment systems help balance the trade-off between the waiting time and the service utilization. However, a bad design can lead to catastrophe in which the waiting time is extremely long. People are unsatisfied when they have to waiting for a long time even if they have made a appointment. Therefore, studying how to design a good appointment system is very important.

In this project, I studied how we can design a good appointment system. I mainly consider the appointment system as a D/M/1 queue, and analyze the property of this model. Afterwards, I solve a optimization problem to obtain an optimal design to get most profit under a criterion.

Assumptions and Definitions

To simplify the appointment system, we make some assumption.

  1. Each person appointed at different time. And we assume every person comes punctually.

  2. The length of interval between arrivals are same.

  3. The system serves arrivals according to "first come first serve" (FCFS). And there is only one server in this system.

  4. The service time of arrivals are independent. Moreover, they has identical exponential distributions.

  5. We assume that the number of arrivals is very large, and thus we can analyze the steady-state system instead of a finite case.

Under these assumptions, the appointment system can be considered as a D/M/1 queue. D/M/1 queue means that the arrival interval are deterministic, and service time is exponential and there is only one server. We mainly analyze D/M/1 model in this project.

Figure 1: An example of the working process in a single server appointment system

Then we define some important variables.

  • \(d\) is the time intervals between each arrivals, and \(\lambda\) is the average arrival rate. Relation \(\lambda = \frac{1}{d}\) holds.

  • \(S\) is the service time of each jobs, and \(\mu\) is the average service rate. By our assumption, \(S \sim Exp(\mu)\).

  • \(\rho\) is the utilization.

  • \(N_A\) is the number of jobs in the system seen by an arrival.

  • \(T\) is the waiting time of each jobs.

Model Analysis

The Utilization and the Expected Busy Period

At the beginning, we consider the utilization and the expected busy period. By definition, We have the utilization \(\rho = \frac{\lambda}{\mu}\). Since \(\lambda = \frac{1}{d}\), we have \(\rho = \frac{1}{\mu d}\).

Then we are going to derive the expected busy period. We let \(B\) denote the busy period. We then let \(I_P\) denote the idle time in each interval. We have \(\frac{E[I_P]}{d} = 1 - \rho\). Thus, we have \[ E[I_P] = d(1 - \rho) . \] We let \(I\) denote the idle period. Then, we have \[ E[I] = E[I \mid I_P > 0] = \frac{E[I_P]}{P\{I_P > 0\}} = \frac{d(1 - \rho)}{1 - \sigma} . \] Since \(\frac{E[B]}{E[B] + E[I]} = \rho\), we have \[ E[B] = E[I] \frac{\rho}{1 - \rho} = \frac{d \rho (1 - \rho)}{(1 - \rho)(1 - \sigma)} = \frac{1}{\mu(1 - \sigma)} . \]

Embedded DTMC and Limiting Distribution

We define \(X_k\) denote a random variable which represent the number of jobs in the system seen by the \(k\)-th arrivals. Since the service time is memoryless, the number of jobs can describe all the information of the system Thus, \(\{X_k\}\) is a discrete time Markov chain. We define the transition probability \(p_{ij} = P\{X_{k+1} = j | X_{k} = i\}\).

To derive the balance equation, we define \[ a_k = P\{\text{there are}~k~\text{departures in a interval}\} = \frac{(\mu d)^k}{k!}e^{-\mu d} \] We additionally define \[ b_k = P\{\text{all}~k~\text{jobs depart in a interval}\} = 1 - \sum_{i=0}^{k} a_i \]

Then, the transition probability is \[ p_{ij} = \left\{\begin{array}{ll} 0, & j > i + 1 \\ a_{i-j+1}, &0 < j \leq i + 1 \\ b_i, &j = 0 \end{array} \right. \] And the Markov chain is shown in Figure 2.

Figure 2: The embedded DTMC of D/M/1 system

Then, the have the balance equation, \[ \begin{aligned} \pi_0 &= b_0 \pi_0 + b_1 \pi_1 + b_2 \pi_2 + \ldots \\ \pi_1 &= a_0 \pi_0 + a_1 \pi_1 + a_2 \pi_2 + \ldots \qquad (1)\\ \pi_2 &= a_0 \pi_1 + a_1 \pi_2 + a_2 \pi_3 + \ldots \\ \pi_3 &= a_0 \pi_2 + a_1 \pi_3 + a_2 \pi_4 + \ldots \\ & \ldots \nonumber\end{aligned} \]

Since the equation has exactly one solution. We guess that \(\frac{\pi_{k+1}}{\pi_k} = \sigma\), and thus \(\pi_{k} = \sigma^k \pi_0\) By equation (1), we have \[ \sigma = a_0 + a_1 \sigma + a_2 \sigma^2 = \sum_{k}^{+\infty}\frac{(\mu d \sigma)^k}{k!} e^{-\mu d}= e^{\mu d \sigma - \mu d} \] Thus, \(\sigma\) should be a solution of the equation \[ \ln(\sigma) = \mu d (\sigma - 1) = \frac{\sigma - 1}{\rho} . \] By taking the derivative, for all \(0 < \rho < 1\), there is exactly one solution \(\sigma\) in \((0, 1)\). So we can consider \(\sigma = \sigma(\rho)\) as a function of \(\rho\). The curve of \(\sigma(\rho)\) is shown in Figure 3.

Figure 3: The relationship between $\sigma$ and $\rho^*$

Thus, we get the limiting distribution. Since \(\sum_{i=0}^{+\infty} \pi_i = \pi_0 \sum_{i=0}^{+\infty} \sigma^i = 1\), we have \(\pi_0 = 1 - \sigma\). And we have \(\pi_k = (1 - \sigma) \sigma^k\).

Let \(N_A\) denote the number of jobs in the system seen by an arrival. We further have \(N_A \sim Geo(1 - \sigma) - 1\). Therefore, we have \[ \begin{aligned} E[N_A] &= \frac{\sigma}{1 - \sigma} \\ Var[N_A] &= \frac{\sigma}{(1 - \sigma)^2}\end{aligned} \]

The Waiting Time

Now, we consider the waiting time. We derive the Laplace transform of the waiting time \(T\) . \[ \begin{aligned} \tilde{T}(s) &= \sum_{k=0}^{+\infty} \pi_n \left(\frac{\mu}{\mu + s}\right)^{k+1} = \sum_{k=0}^{+\infty} (1 - \sigma) \sigma^n \left(\frac{\mu}{\mu + s}\right)^{k+1} \\ &= \frac{\mu(1 - \sigma)}{\mu + s} \sum_{k=0}^{+\infty} \left(\frac{\mu\sigma}{\mu+s}\right)^k = \frac{\mu(1 - \sigma)}{\mu(1-\sigma) + s}\end{aligned} \]

Thus, \(T \sim Exp(\mu(1 - \sigma))\). We have \[ \begin{aligned} E[T] &= \frac{1}{\mu(1 - \sigma)} \\ Var[T] &= \frac{1}{\mu^2(1 - \sigma)^2}\end{aligned} \]

Comparison with M/M/1 System

In the last part of this section, we compare the result of D/M/1 with M/M/1 system.

Recall that \[ \begin{aligned} E[T]^{M/M/1} &= \frac{1}{\mu(1 - \rho)} \quad E[N]^{M/M/1} = \frac{\rho}{1 - \rho} \\ E[T]^{D/M/1} &= \frac{1}{\mu(1 - \sigma)} \quad E[N]^{D/M/1} = E[T]^{D/M/1}\lambda = \frac{\rho}{1 - \sigma} \quad\end{aligned} \]

We can see \(E[T]\), as well as \(E[N]\), in D/M/1 is smaller than M/M/1 by a factor \(\frac{1 - \rho}{1 - \sigma}\) since \(\rho < \sigma\) holds for all \(0 < \rho < 1\). This can be explained by the fact that the uncertainties of arrivals is reduced by appointment, and thus, the waiting time is smaller. The curve of \(E[T]\) in both model is shown in Figure 4.

Figure 4: E[T] in M/M/1 and D/M/1 (assuming $\mu = 1$)

We can further discover that PASTA property doesn't hold for D/M/1 model since \(E[N_A]^{D/M/1} = \frac{\sigma}{1 - \sigma} \neq E[N]^{D/M/1}\). This result also corresponds to our intuition because \(N\) at the end of a period is no larger than \(N\) in the same period.

Designing a Best Appointment System

When we design a appointment system, we assume \(\mu\) is fixed, and \(d\) is determined by us. we need to balance a trade-off between the waiting time and the utilization in determining the value of \(d\). If \(d\) is too small, the number of arrivals in a unit time is small, and thus the utilization is small. Conversely, if \(d\) is too large, the expected waiting time is large.

Our objective can be maximizing our profit. The profit is influenced by two parts. The first part is that we can earn \(A\) for each arrival. The second part is that we cost \(B\) per unit time for the waiting time of each arrival. Our goal can be written as the following optimization problem, \[ \begin{aligned} \max_d \quad &\tau \lambda\left(A - B \cdot E[T \mid \text{arrivals in }\tau] \right) \quad (\text{given a sufficiently large }\tau)\\ \text{s.t.} \quad &\ln(\sigma) = \mu d (\sigma - 1), \quad d > \mu\end{aligned} \]

In order to simplify the equation, we let \(\gamma = \frac{B}{\mu A}\). Without calculation, we know that if \(\gamma \geq 1\), the optimal scheme is \(\gamma=0\), which is meaningless for appointment system. Thus, we only consider \(0 < \gamma < 1\). Besides, we use \(\rho = \frac{1}{\mu d}\) instead of \(d\) in our derivation. Now, the optimization problem can be written as following, \[ \begin{aligned} \max_\rho \quad &\rho \left(1 - \gamma \frac{1}{(1 - \sigma)}\right) \\ \text{s.t.} \quad &\ln(\sigma) = \frac{\sigma - 1}{\rho}, 0 < \rho < 1\end{aligned} \]

Taking the derivative of the objective with respect of \(\rho\), we have \[ 1 - \gamma \frac{1}{1 - \sigma} - \rho \gamma \frac{\sigma'}{(1 - \sigma)^2} = 0 \] Then we have \[ \gamma = \frac{(1 - \gamma)^2}{(1 - \gamma) + \rho \gamma'} \qquad (2) \]

Now, we take the derivative of \(\ln(\sigma) = \frac{\sigma - 1}{\rho}\) with respect of \(\rho\), we have \[ \frac{\sigma'}{\sigma} = \frac{\rho\sigma' - (\rho - 1)}{\rho^2} \] Then we have \[ \sigma' = \frac{\sigma(\sigma - 1)}{\rho \sigma - \rho^2} = \frac{\sigma(\sigma - 1)}{\rho(\sigma - \rho)} \]

Substituting \(\sigma'\) into equation (2), we have \[ \gamma = \frac{(1 - \sigma^2)}{(1 - \sigma) + \frac{(1 -\sigma) \sigma}{\rho - \sigma}} = (1 - \sigma)(1 - \frac{\sigma}{\rho}) \qquad (3) \]

We define \(F(\rho) = (1 - \sigma(\rho))(1 - \frac{\sigma(\rho)}{\rho})\). We have \(F(0) = 1\) and \(F(1) = 0\). By taking the derivative of \(F(\rho)\), we know that \(F\) is a monotonically decreasing function. Thus, there is exactly one solution \(\rho^*\) for equation (3), which satisfy \(\gamma = F(\rho^*)\). By simple examination, \(\rho^*\) leads to the maximum of the objective. The optimal \(\rho\) with respect of \(\gamma\) is shown in Figure 5.

Therefore, the optimal \(d\) is \[ d^* = \frac{1}{\mu \rho^*} = \frac{1}{\mu F^{-1}(\gamma)} \]

Figure 5: The relationship between $\rho$ and $\gamma$

Extensions: Multiple Servers and Batch Arrivals

I also tried to analyze some other version of appointment system. However, I failed to get any useful result even for the simplest case. I show some of my progress so far in this section.

System with Two Servers, D/M/2

We similarly define \(X_n\) denote the number of jobs in the system seen by the \(n\)-th arrival. Then \(\{X_k\}\) is a Markov chain. We define \(p_{ij} = P\{X_{k+1} = j | X_{k} = i\}\). We define \[ \begin{aligned} a_k &= P\{\text{there are}~k~\text{departures in a interval}\} = \frac{(2\mu d)^k}{k!}e^{-2\mu d} \\ b_k &= P\{\text{all}~k~\text{jobs except one depart in a interval}\} \\ c_k &= P\{\text{all}~k~\text{jobs depart in a interval}\} = 1 - b_k - \sum_{i=0}^{k-1} a_i\end{aligned} \] Then, the transition probability is \[ p_{ij} = \left\{\begin{array}{ll} 0, & j > i + 1 \\ a_{i-j+1}, &1 < j \leq i + 1 \\ b_i, &j = 1 \\ c_i, &j = 0 \end{array} \right. \] And the Markov chain is shown in Figure 6.

Figure 6: The embedded DTMC of D/M/2 system

Then, we have the balance equation, \[ \begin{aligned} \pi_0 &= c_0 \pi_0 + c_1 \pi_1 + c_2 \pi_2 + \ldots \\ \pi_1 &= b_0 \pi_0 + b_1 \pi_1 + b_2 \pi_2 + \ldots \\ \pi_2 &= a_0 \pi_1 + a_1 \pi_2 + a_2 \pi_3 + \ldots \\ \pi_3 &= a_0 \pi_2 + a_1 \pi_3 + a_2 \pi_4 + \ldots \\ & \ldots \nonumber\end{aligned} \]

However, I fail to solve this equation because I do not know how to derive \(b_k\) in a pretty way. Moreover, I do not know how to solve this equation without guessing.

Two Arrivals Each Time, D\(^2\)/M/1

We similarly define \(X_n\) denote the number of jobs in the system seen by the \(n\)-th arrival. Then \(\{X_k\}\) is a Markov chain. We define \(p_{ij} = P\{X_{k+1} = j | X_{k} = i\}\). We define \[ \begin{aligned} a_k &= P\{\text{there are}~k~\text{departures in a interval}\} = \frac{(\mu d)^k}{k!}e^{-\mu d} \\ b_k &= P\{\text{all}~k~\text{jobs depart in a interval}\} = 1 - \sum_{i=0}^{k+1} a_i\end{aligned} \] Then, the transition probability is \[ p_{ij} = \left\{\begin{array}{ll} 0, & j > i + 2 \\ a_{i-j+2}, &0 < j \leq i + 2 \\ b_i, &j = 0 \end{array} \right. \] And the Markov chain is shown in Figure 7.

Figure 7: The embedded DTMC of D^2/M/1 system

Then, we have the balance equation, \[ \begin{aligned} \pi_0 &= c_0 \pi_0 + c_1 \pi_1 + c_2 \pi_2 + \ldots \\ \pi_1 &= ~~~~~~~~~~~~a_1 \pi_0 + a_2 \pi_1 + \ldots \\ \pi_2 &= a_0 \pi_0 + a_1 \pi_1 + a_2 \pi_2 + \ldots \\ \pi_3 &= a_0 \pi_1 + a_1 \pi_2 + a_2 \pi_3 + \ldots \\ & \ldots \end{aligned} \]

However, I fail to solve this equation as well. Even though the equation is very similar to D/M/1, the method of D/M/1 cannot work here. And I also do not know how to use transform method as well.

Future Works

There are some other idea which can be done in the future work, which do not contain in this project due to time and capability limitation.

  1. We only consider the arrive time as a fixed point in this project. But in reality, the arrival time has some randomness. Also there is a probability that the custom do not show at the appointment time. Moreover, the randomness of arrival time and no-show probability may be influenced by the waiting time.

  2. We only consider the server only serve for people who have made appointment. We can further consider how the system serve for both arrivals with appointments and without appointments.

  3. We can also consider whether there are some policies which allow preemptive or use job size information to improve the performance of the appointment system.

Conclusion

In this project, I studied how we design a best appointment system under a criterion. I consider the appointment system as a D/M/1 queue, and analyze some quantities and properties of D/M/1 queue. Using embedded DTMC, I obtain the distribution of the number of jobs seen by an arrival and the waiting time. I solve a optimization problem and get an optimal solution which can get the maximum profit. The result shows that the the appointment system has a significant improvement comparing with M/M/1 queuing.

Reference

[1] Andreas L¨opker and David Perry. The idle period of the finite g/m/1 queue with an interpretation in risk theory. Queueing Systems, 64(4):395–407, 2010.

[2] Ivo Adan, Onno Boxma, and David Perry. The g/m/1 queue revisited. Mathematical Methods of Operations Research, 62(3):437–452, 2005.

[3] Birger Jansson. Choosing a good appointment system—a study of queues of the type (d, m, 1). Operations Research, 14(2):292–312, 1966.

[4] Jianzhe Luo. Queueing Approaches to Appointment System Design. PhD thesis, The University of North Carolina at Chapel Hill, 2012.