5. About G/G queues

5.1 Aim of this chapter

The modeling of any actual system must take waiting processes into account (Park and Miller, 1988). In what follows, only the simplest waiting system will be considered, the so-called waiting queues. We will explore two kinds of economical questions, namely :

• [Shift] the waiting process, in order to place the waiting burden on the less costly part of the system... and even on someone else, client or supplier. For example, using more repairmen to take care of a given assembly line will shorten the mean time before repair when a failure occurs (and the losses due to the line inactivity) but, on the other hand, this will increase the time when repairmen are waiting for a failure... and the corresponding cost.
• [Reduce] the waiting process. It will be seen that waiting is caused by variances. In other word, reducing the variances of arrivals and services is the only way to actually reduce the whole waiting process.

Definition 5.1.1   A waiting queue (cf. fig:waitfile) is, by definition, a model whose behavior is as follows:

• [Customers] are the objects/persons that are processed in the system (waiting room + service room). It is assumed that customers arrive one at a time and are served in FIFO order (i.e. first in, first out).
• [Waiting room] is assumed to be infinite, in order that a customer arriving in a busy (i.e. not empty) system can find a place to wait until it can be served.
• [Inter-arrival] is the time between two arrivals. It is assumed that inter-arrival times are independent and distributed according to a fixed law (that doesn't depends on the size of the queue or on anything else). Thus:
  $$Pr\left(interarrival\in\left[t,\, t+\, \mathrm{d}t\right]=a\left(t\right)\,\, \mathrm{d}t\right)$$

• [Sojourn] is the whole time spent by the customer in the system (sojourn time = waiting time + service time)
• [Service] is the time actually used to serve the customer. It is assume that the service times are independent and distributed according to a fixed law (that doesn't depends on the size of the queue or on anything else). Thus:
  $$Pr\left(service\in\left[t,\, t+\, \mathrm{d}t\right]=b\left(t\right)\,\, \mathrm{d}t\right)$$

FIG. 5.1: Elementary waiting queue

Remark 5.1.2   In an actual system, the independency hypothesis on inter-arrival is quite realistic. The independency hypothesis on services is more dubious.

Proposition 5.1.3   A necessary condition for a proper behavior of the queue is the following: the ability of the system to clear the queue, measured by the service flow $\mu\doteq1/\mathrm{E}\left(b\right)$, must be greater than the ability of the arrival process to provide new customers, measured by the arrival flow $\lambda\doteq1/\mathrm{E}\left(a\right)$. In other words, on must have:

$$\lambda=\rho\,\mu\quad where\quad\rho<1$$

5.2 How to simulate a waiting queue

The aim of the following implementation is not a better speed of execution, but a better understanding of what is undertaken.

Definition 5.2.1   An event is a pair $\left[d,\, X\right]$ where $d$ is the delay before the event occurs and $X$ is either A or D, according to the nature of the event (Arrival or Departure).

Definition 5.2.2   The agenda is a list of events, sorted by increasing remaining delays before occurrence. With the given hypotheses, the agenda contains exactly one event A and some events D (as much as sojourning customers).

Definition 5.2.3   The workload of the server is remaining time before the departure of the last arrived customer if any, or is equal to zero.

Algorithm 5.2.4   The arrival of a new customer creates two events : the future arrival of the next to come customer and the future departure of the incoming customer. By the independence hypotheses, both these values can be generated as soon as the customer arrives, leading to alg:new-client.

Algorithm 5.2.5   Processing the next to come event is done as follows. The elapsed time before the occurrence of this event is read and the delays before occurrence of all the other events are recomputed time (and also the workload). If the occurring event is an arrival, the new procedure is called (alg:Gestion-d'un-evenement).

Algorithm 5.2.6   The "server-side observations" are done by cumulating the time spent while a given number of customers were sojourning in the system. In alg:Observations-serveur, the durations table is implemented according to a "create on the fly" scheme.

Algorithm 5.2.7   The "customer-side observations" are the records, for each new customer, of the waiting time, the (total) sojourn time and the number of formerly arrived customers present at the given customer arrival. A full registration has been chosen rather than tallying on the fly into predefined intervals (alg:Observations-clients).

Remark 5.2.8   Given the number of data structures to initialize, it can be useful to summarize all these initializations into a unique procedure. One obtains alg:Initialisation-des-tables.

5.3 Simulation of a U/U queue

The next to come cha:M/M-Queues will be devoted to M/M queues. One cannot understand how these queues are special without a former knowledge of what happens with other laws of service and arrival. Additionally, U-shaped services are not so uncommon. In all the following examples, the average inter-arrival is $1/\lambda=20$ (say : minutes), and the average service is $1/\mu=15$.

Example 5.3.1   With very small variances, no waiting process occurs at all. When using $a\in\left[20\pm2\right]$ and $b\in\left[15\pm1\right]$, the successive values of the agenda looks like:

$[[14.64222139,\,\mathrm{D}],\,[19.70967868,\, A]]$
$[[5.06745729,\, A]]$
$[[14.94851229,\,\mathrm{D}],\,[19.37453230,\, A]]$
$[[4.42602001,\, A]]$
$[[15.49350766,\,\mathrm{D}],\,[20.23383488,\, A]]$
$[[4.74032722,\, A]]$

In this example, even the largest service time can't overflow the shortest inter-arrival time.

Example 5.3.2   When using $a\in\left[20\pm4\right]$ and $b\in\left[15\pm2\right]$, there is a (very small) probability that an arrival occurs during a service, inducing a (small) waiting time for the arriving customer. In a simulation of $10000$ events, concerning $5000$ customers, the following durations have been registered : $25076\mathrm{mn}$ in the $N=0$ state (empty system), $74913\mathrm{mn}$ in the $N=1$ state (one customer being served while the waiting room is empty) and $26\mathrm{mn}$ in the $N=2$ state (one customer being served, while another waits). The corresponding frequency vector is therefore:

$$\left[0.251,\,0.749,\,0.0003\right]$$

Definition 5.3.3   This vector will be referred as the (experimental) occupancy distribution of the queue. Each entry of this vector gives the ratio of the time elapsed while a given number of customers were sojourning in the system by the total time of the observation.

Exercise 5.3.4   Obtain the (exact value of the) probability that an arrival occurs during a service in the preceeding exercise.

Example 5.3.5   When using $a\in\left[20\pm10\right]$ and $b\in\left[15\pm7\right]$, the waiting process increases and one obtained occupancy vector is:

$$occupancy=\left[0.253,\,0.656,\,0.089,\,0.002\right]$$

Example 5.3.6   We will now examine with more details the case $a\in\left[20\pm15\right]$ and $b\in\left[15\pm10\right]$. A simulation of $20000$ customers has given a total duration of $402231\mathrm{mn}$ and the following occupancy vector:

$$[.2545,\,.5189,\,.1813,\,.0365,\,.0072,\,.0012,\,.0003,\,.00007]$$

On the other hand, the numbers of formerly arrived customers, as registered by the incoming client (and the corresponding frequencies) were:

$$\left[\begin{array}{rrrrrcr} 10285 & 7478 & 1812 & 347 & 63 & 10 & 5\\ .5142 & .3739 & .0906 & .0174 & .0032 & .0005 & .0002\end{array}\right]$$

The histograms of both frequencies are drawn in fig:Server-versus-customer where the customer point of view is in light grey, the server one in medium grey, and the common part in dark grey. This figure shows how these two points of view are strongly different and appear as being contradictory, giving an illustration of the number/time paradox (that will be discussed in sec:number-vs-mass).

FIG. 5.2: Server side and customer side points of view

The distribution of the waiting time is given fig:uu-waiting, where the Dirac relative to $waiting=0$ has been drawn as an ordinary bar, labeled "none".

FIG. 5.3: Waiting time distribution

Exercise 5.3.7   In the simulation described above, the following values have been obtained. Check them for consistency with hypotheses :

$$mean\left(sojourn\right)=20.67889063 ; mean\left(waiting\right)=5.685457230$$

$$var\left(sojourn\right)=120.9318014 ; var\left(waiting\right)=86.78207865$$

Exercise 5.3.8   Check data from exa:uu-simul against Little's theorem.

5.4 The number vs time paradox

Definition 5.4.1   The length of the queue is the total number of customers present in the system. Period.

Remark 5.4.2   The number of waiting customers is not the length of the queue, since the later is the number of sojourning customers.

Theorem 5.4.3 (Little)   For any iid arrivals, define $N$ as the average length of the queue over the time, $T$ as the average sojourn time of a customer and $\lambda$ as the arrival flow. Then

$$N=\lambda\, T$$

Preuve. Define (according to fig:Graphical-Little, extracted from Sinclair, 2006)
$\alpha\left(t\right)\equiv$ number of arrivals in the interval $\left(0,\, t\right)$,
$\delta\left(t\right)\equiv$ number of departure in the interval $\left(0,\, t\right)$,
$N\left(t\right)\equiv$ number of sojourning customers at time $t$
$\gamma\left(t\right)\equiv$ accumulated value of the customer $\times$ seconds product.

The shaded area between the arrival and departure curves is $\gamma\left(t\right)$ , while the average customer's flow during $\left(0,\, t\right)$ is $\lambda_{t}=\alpha\left(t\right)/t$, the average number of sojourning customers is $N_{t}=\gamma\left(t\right)/t$ and the average time $T_{t}$ a customer sojourns in the system during $\left(0,\, t\right)$ is $\gamma\left(t\right)/\alpha\left(t\right)$. Therefore $N_{t}=\lambda_{t}\, T_{t}$ and the result follows (assuming the convergence of $N_{t},$ $T_{t}$ and $\lambda_{t}$). $\qedsymbol$

FIG. 5.4: Graphical proof of the Little's theorem (from Sinclair, 2006).

Definition 5.4.4   The "number average" of a quantity related to a queuing system is what is obtained when using a "one customer, one vote" scheme (i.e. acting as when computing the average sojourn time $T$ in thm:Little). On the other hand, the "time average" of the same quantity is what is obtained when using a "one time tick, one vote" (i.e. acting as when computing the average occupancy $N$ in thm:Little).

Definition 5.4.5   Let $x$ be a positive random variable, with probability distribution function $f$: $Pr\left(x\in\left[t,\, t+\, \mathrm{d}t\right]\right)=f\left(t\right)\,\, \mathrm{d}t$. The "weight distribution" is the pdf of a new positive variable $X$, characterized by

$$Pr\left(X\in\left[t,\, t+\, \mathrm... ...}\, f\left(t\right)\,\, \mathrm{d}t\qquad where\quad m=\mathrm{E}\left(x\right)$$

In this context, the original pdf will be referred as the "number distribution" of the variable.

Remark 5.4.6   The normalization factor $1/m$ in the above formula comes from $\int F\left(t\right)\, \mathrm{d}t=1$.

Proposition 5.4.7 (polydispersity)   Let $\mathrm{E}_{w}\left(X\right)$ be the weight expectation of $X$ (using pdf $F$) and $\mathrm{E}\left(x\right)=\mathrm{E}_{n}\left(x\right)$ be the number expectation of $x$ (using pdf $f$). Then:

$$\mathrm{E}_{w}\left(X\right)=\mathrm{E}_{n}\left(x\right)\times\left(1+\frac{\mathrm{var}\left(x\right)}{\mathrm{E}\left(x\right)^{2}}\right)$$

Preuve. Obvious from definitions and the well known: $\mathrm{E}\left(x^{2}\right)=\mathrm{var}\left(x\right)+\mathrm{E}\left(x\right)^{2}$. Largely in use (Melcion, 2000), this is nevertheless a worshiped formula among polymerists. $\qedsymbol$

Definition 5.4.8   When a customer arrives in a busy queue, another customer is being served. The residual service is the random variable defined as the delay, observed by the incoming customer, that remains before completion of the service that was running.

Example 5.4.9   In exa:uu-simul, the data of tab:uu-cumulated-quantities have been recorded. For example, when a customer arrives in a queue where 3 clients are yet sojourning, then incoming, busy and yet-waiting are, respectively, increased by 1, 1, 2.

Therefore, the cumulated sojourn time can be split in two parts : on the one hand, the sum of $22760$ ordinary services (mean $1/\mu=15\mathrm{mn}$) and, on the other hand, the sum $9715$ residual services. This leads to $7.42$ as the (experimental) value of the average residual service, and to fig:uu-residual for the whole experimental distribution of the residual service.

TAB. 5.1: Cumulated quantities (as observed by customers)

TAB. 5.2: Cumulated quantities (without makeimage)

cumulated quantities

incoming customers

FIG. 5.5: Experimental distribution of the residual service

Exercise 5.4.10   When $N$ is great enough, the incoming customer arrive quite uniformly during the running service, and the weight distribution can be applied. Determine this distribution when the number distribution is uniform.

Exercise 5.4.11   Determine the distribution to use when assuming that the incoming customer arrives in an U/U queue when a service is running, but the waiting room is empty.