5.2 Applications of the M(n)/M(n)/1 queueing model

In this section we apply the tools developed above to a number of interesting queueing systems. First, we discuss how to use the \(M(n)/M(n)/1\) queue to organize a part of a production process. Second, we show how to plan the number of servers at a call center such that the average queue length remains small.

Riley is an operations manager at a factory that produces custom metal parts for various industries. Riley’s factory has a single heat treatment furnace to temper the metal parts. Recently, Riley noticed an increase in customer orders, leading to long delays and dissatisfied clients.

1. Should Riley sometimes block jobs to control the waiting time?
2. Should Riley buy another oven to increase the capacity?
3. If Riley bought a second oven, the utilization of both ovens may become quite low. However, as an oven is costly to heat up, it may be favorable to only switch on a second oven when queues are long.

To compare the effect of these different strategies, Riley hires us to model the operation of the oven using queueing theory. We consider the following metrics: average job waiting times, average number of jobs in the system, machine utilization, and job acceptance rate. For ease¹¹At a later stage we can make more complicated models., we assume that jobs arrive as a Poisson process with a rate \(\lambda\) jobs per hour, and production times are \(\sim \Exp{\mu}\) with \(1/\mu = \E S\).

We implemented the level-crossing recursions and the KPI formulas from the previous section for each choice of the arrival and service rates. For the numerical comparison, take \(\lambda=1.9\) and \(\mu=2\) per hour. The results are as follows. Here, \(\bar\lambda\) is the acceptance rate and \(\rho\) is the capacity utilization.

With one oven, the high utilization leads to a long expected waiting time. Limiting the system to \(K=10\) reduces the expected waiting time considerably, at the cost of rejecting about \(7\%\) of the jobs. Keeping two ovens running makes the expected waiting time almost negligible, but leaves much capacity unused. Switching on the second oven only when \(n\geq5\) provides a compromise: the expected waiting time is \(0.79\), while the first and second ovens are busy \(81\%\) and \(14\%\) of the time, respectively.

As a numerical check, increasing \(K\) from \(10\) to \(1000\) recovers the results of the \(M/M/1\) model without blocking.

Let us next discuss an example of employee planning at a call center. Here we keep the models simple, but we include all necessary steps to solve a realistic planning problem.

We start with specifying the arrival process. It is reasonable to model it as a Poisson process, as there are many potential customers, each choosing with a small probability of calling at a certain moment in time. Thus, we only have to characterize the arrival rate. Estimating this for a call center is easy because all calls are registered.

from pathlib import Path
import sys
sys.path.insert(0, str((Path.home() / "vakken" / "course-common" / "scripts").resolve()))
from render_tikz import render_tikz

render_tikz(r"""
\begin{tikzpicture}[scale=.5]
    %axis
    \draw[->] (0,0) -- coordinate (x axis mid) (13.5,0);
    \draw[->] (0,0) -- coordinate (y axis mid) (0,5.5);
    %ticks
    \foreach \x in {0,...,8}
 \pgfmathsetmacro{\my}{int(\x+8)}
        \draw (\x,1pt) -- (\x,-3pt)
            node[anchor=north] {$\my$};
    \foreach \y in {0,...,5}
 \pgfmathsetmacro{\my}{int(\y*40)}
        \draw (1pt,\y) -- (-3pt,\y)
            node[anchor=east] {\my};
%labels
\node[below=0.6cm] at (x axis mid) {hour};

\draw (0,1)--(1,1);
\draw (1,2)--(2,2);
\draw (2,2.6)--(3,2.6);
\draw (3,2.8)--(4,2.8);
\draw (4,3.)--(5,3.);
\draw (5,3.1)--(6,3.1);
\draw (6,2.7)--(7,2.7);
\draw (7,1.9)--(8,1.9);
\end{tikzpicture}
""", "../figures/demand_profile.png")

It is common to use a demand profile that shows the average number of customers arriving per hour. Then we model the arrivals as a Poisson process with an arrival rate that is constant during a certain hour, as specified by the demand profile.

⊕
Figure 5.1: A demand profile.

It is also easy to find the service distribution; for ease, we model the service time distribution as exponential with mean \(1.5\) minutes.

For the service objective we prefer to keep the average number of jobs in the system such that \(\E \L \leq 5\).²²Other KPIs are also possible to use.

Let us model the situation as an \(M/M/1\) queue with one server that works as fast as \(c\) single servers combined. Solving for \(c\) in the inequality \(\E \L \leq 5\) gives³³\(\E \L = \rho/(1-\rho) \implies \rho = \E \L/(\E \L + 1)\) and \(\rho=\lambda \E S /c\).

where, with the above estimate, \(\E{S}=1.5/60\) hour. It is easy to apply this formula. For instance, we see in the demand profile Fig. 5.1 that \(\lambda= 120\) customers per hour between 12 and 13, hence we need \(c\approx 3.6 = 4\) employees for that period.

With this we can find a formula to convert the demand profile into a load profile to specify the minimal number of servers per hour needed to meet the service objective.

The last step in the planning process is to cover the load profile with service shifts. This is typically not easy since shifts have to satisfy all kinds of restrictions with respect to breaks and durations. Moreover, shifts can also have different costs: evening shifts are typically more expensive per hour.

The usual way to solve such covering problems is by means of an integer programming problem. For instance, suppose only 4 shift plans are available as shown at the right.⁴⁴1. \(++-++\) 2. \(+++-+\) 3. \(++-+++\) 4. \(+++-++\). Shift plans. A \(+\) indicates a working hour and \(-\) a break of an hour.

For the optimization, let \(x_i\) be the number of shifts of type \(i\) and \(c_i\) the cost of this type. Then the problem is to solve \(\min \sum_i c_i x_i\), such that for all hours \(t\) the shifts cover the load, that is, \(\sum_i x_i \1{t \in s_i} \geq 0.03 \lambda_t\). (We write \(t\in s_i\) if hour \(t\) is covered by shift type \(i\).)

The next exercises require some modeling skills. Hence, they may be quite hard even though the formulas are simple.