02 - Fundamentals fo Queuing Theory - OMT

Queues appear when a flow of vehicles, persons or objects wants to receive a service that implies a restriction. Typically, services have a limited capacity or are offered only with some frequency, which may lead to queues, delays and waits.

The subject that studies queues is referred to Queuing Theory (see also [[03. Variabili Aleatorie#Teoria delle code]], [[05. Teoria del Deflusso#Teoria delle code]]).

Most of the complexities of queuing theory come from the stochastic nature of the processes involved.

Components of a queuing system

Server: the restriction
Storage: where the costumer waits
Arrivals: the ones that feed the queue
Departures: the yield after service

%%🖋 Edit in Excalidraw%%

Server

Server disposition

In any system, there can be more than 1 server. The $n$ servers, can be

• [[#Servers in parallel]]
• [[#Servers in series]]

Servers in parallel

When the servers are localised in parallel, they can work at the same time. These are differentiated based on how the queue works:

• [[#Decentralised system]]
• [[#Centralised queue]]

One problem that might arise with parallel service, is that the servers are not positioned in space in an efficient way. It may happen that the queue of one server blocks some other server. This could happen, for example, at a petrol station where two pumps are one after the other and there is not enough space for cars to overtake each other.

Decentralised system

In a decentralised system, each server has its own queue.

%%🖋 Edit in Excalidraw%%

Centralised queue

In a centralized queue, there are multiple servers but only 1 queue.

%%🖋 Edit in Excalidraw%%

The centralised queue, if well managed, can maximize the capacity and efficiency of the system. In fact, in this case, no server will ever be idle, while there are other servers working.

It also guarantees the [[#First Come First Serves - FCFS]] functioning.

In these kind of systems, it is important to implement adequate information system that assigns customers to servers at due time. This needs to ensure that there is no idle server at any time.

This can be challenging, especially when it takes a long time for the costumer to get to the server from the end of the queue (think of container ships waiting outside a port).

Servers in series

Tandem queues

%%🖋 Edit in Excalidraw%%

In this kind of systems costumers need to undertake several steps to receive a complete service.

For example, in an airport, a passenger has first to check-in, thank go through security, and finally queue to board the plane. Seen as a whole, this is a tandem queue.

In this scenario, the departure from the previous server, is the arrival of the subsequent one.

A better explanation of this kind of systems is provided in the section [[#Tandem queueing system]]

Storage

Arrivals

Departures

Queuing disciplines

Queuing discipline is a non-physical component of a queuing system. It refers to the rules which determine in which order the costumers are served.

The most common ones are:

• [[#First Come First Serves - FCFS]]
• [[#Last Come Last Serves - LCLS]]
• [[#Service in Random Order - SIRO]]
• [[#Round Robin - RR]]

Sometimes, there can be priorities assigned to some kind of costumers, leading to a new type of discipline:

• [[#Early Due Date First - EDDF]]
• [[#Shortest Service Time First - SSTF]]

First Come First Serves - FCFS

This is the most common discipline when dealing with human costumers.

This doesn't mean that the first costumer to enter will also be the first one to exit as, with [[#Servers in parallel]], some server may be faster than another allowing for overtakes in the system.

Last Come First Serves - LCFS

This happens when the [[#Storage]] is in a closed space and the entrance and exit are the same "door".

For example an airport shuttle bus will unload first the passengers that boarded the bus at last and viceversa.

Service in Random Order - SIRO

This system is mostly applied to industrial processes where the costumer are different items in a production line.

Round Robin - RR

This discipline applies in the communication networks.

Early Due Date First - EDDF

Shortest Service Time First - SSTF

Cumulative plot

Properties of the cumulative plot:

• It's a discrete function
• It's always increasing or, at most, constant

The flow of vehicles or passengers $q$ can be calculated starting from the cumulative plot as:

where

• $T=t_j-t_i$ the period of observation

The plot can be obtained in 2 ways:

• Every time a customer enters the system, the time and the cumulative number of customer is recorded
• Every a predefined $\mathrm{\Delta }t$, the cumulative number of customer that entered the system in that time interval is recored

When a large number of customer is recorded, the jumps of the $N(t)$ function become meaningfulness. So, the function is usually replaced by a continuous interpolation.

%%🖋 Edit in Excalidraw%%

In this situation, we can calculate the instantaneous flow $q_{(t)}$ as:

Input-output diagram

An input-output diagram is the overlay of 2 [[#Cumulative plot]]:

• $A(t)=N(t,x_0):$ cumulative plot measured at location $x_0$, before the system being measured. In other words, the [[#Arrivals]]

• $D(t)=N(t,x_1):$ cumulative plot measured at location $x_1$, after the system being measured. In other words, the #Departures

• If the $A(t)$ curve is not measured exactly at the entrance of the system of interest, don't we overestimate the delay time in the system? ✅ 2024-10-29

%%🖋 Edit in Excalidraw%%

The diagram above is an input-output diagram.

Notice that the horizontal distance between the 2 curves at a given number of cumulative costumers, $n_1$, is the time spent by that costumer in the system. This time includes:

• Potential delays
• Free flow service time

Instead, the vertical distance between the 2 curves at a given instant $t_1$, is the customer accumulation in the system. This includes:

• The customer being served at the moment
• The customers waiting to be served

In the diagram above, other than the input-output diagram, the amount of customers in service and in queue at any given time is also shown:

%%🖋 Edit in Excalidraw%%

A logistic curve

We will now consider an [[#Input-output diagram]] with a large number of customers, so that the curves can be seen as continuous functions.

%%🖋 Edit in Excalidraw%%

In the input-output diagram, the Arrival curve $A(t)$ usually takes the shape of a logistic curve.

The arrival rate is always relatively small at the two extremes while it picks in the middle (the arrival rate, $\lambda$, is given by the slope of the arrival curve). This is because, as humans, we tend to want the same service at about the same time. This pick rate is theoretically unbounded.

The departure curve instead, has a fixed maximum rate, $\mu$, equal to the Capacity of the system. So, this slope is always bounded.

From a normal [[#Input-output diagram]] we can easily read the sum of the service time and delay, and the total accumulation (number of customer being served + customers queuing).

It is useful to be able to read directly the delay and the excess accumulation. This can be done through the [[#Virtual Arrivals Curve]]

3D representation of input-output diagram

If we want to visualize both vehicles trajectories and input-output diagram on the same chart, we can do so in a 3D diagram:

The projection of this diagram on the ($x,t$) plane gives the trajectories, while the projection onto the $(N,t)$ plane gives the input-output diagram.

We can also look at the two projection one under the other to visualize everything on a single plane:

• If at one point there is queuing (accumulation), shouldn't the $x,t$ diagram show the trajectory going horizontal for a bit? ✅ 2024-10-28
  • Not necessarily: if more veh are being served and they don't need to stop, than this is correct

Virtual Arrivals Curve

What we obtain:

• [[#Excess accumulation]]
  • #Average excess accumulation
• [[#Delay]]
  • #Average delay per costumer

Excess accumulation

The Excess accumulation can be obtained as the vertical distance in the $N-t$ diagram between the [[#Virtual Arrivals Curve]] and the [[#Departures]] curve.

%%🖋 Edit in Excalidraw%%

Average excess accumulation

%%🖋 Edit in Excalidraw%%

We define the area

as the total aggregated delay in the period $t_i,t_j$

Take some time to think on the meaning of the average excess accumulation:

Delay

Delay can be obtained as the horizontal distance in the $N-t$ diagram between the [[#Virtual Arrivals Curve]] and the [[#Departures]] curve.

%%🖋 Edit in Excalidraw%%

Average delay per costumer

%%🖋 Edit in Excalidraw%%

We define the area:$$
W_{2} \quad \rm[costumers]

\begin{align}
\text{Knowns: }&
\begin{cases}
V(t): \text{Measured when there are few people} \
\mu : \text{Max service flow (it's a property of the facility)}
\end{cases} \ \

\text{Unknowns: }&
\begin{cases}
\overline{w}\
\overline{Q}
\end{cases} \quad \Longrightarrow\text{We need the }D(t)
\end

\begin{cases}
D(t) < V(t) \quad \forall t \
\dot{D}(t) < \mu \quad \forall t
\end

n = \begin{cases}
\lambda t^{} \
\mu (t^{}-R)
\end

\lambda t^{} = \mu (t^{} -R)

\begin{align}
\lambda t^{} &= \mu (t^{} -R) \
\lambda t^{} &= \mu t^{} - \mu R \
(\lambda -\mu )t^{} &= -\mu R \
(\mu - \lambda )t^{} &= \mu R \
t^{*} &= \frac{\mu R}{\mu -\lambda }
\end

n = \lambda t^{*} = \frac{\mu \lambda R}{\mu -\lambda }

W = \frac{1}{2} Rn = \frac{1}{2} \frac{\mu \lambda R^{2}}{\mu -\lambda }

\overline{w} = \frac{W}{n'} = \frac{\frac{1}{2} \frac{\mu \lambda R^{2}}{\mu -\lambda }}{\lambda (R+G)} = \frac{1}{2} \frac{\mu R^{2}}{(\mu -\lambda)(R+G) }

\lambda (R+G) < \mu G

\frac{\lambda}{\mu} < \frac{G}

\overline{w} = \frac{W}

\lambda > \mu_{2} > \mu_

\mu_{1} > \mu_{2} > \mu_

Z_{tot} = Z_{A} + Z_

\min_\mu Z = \min_\mu (Z_{A}+ Z_{u})

\frac{\partial Z}{\partial \mu} \stackrel{!}{=}0