7.4 Measures of Performance
There are various measures that one can use to assess the quality of a queuing system. These are:
L: the average number of customers in the system;
LQ: the average number of customers in the system;
w: the average time spent in the system;
wQ: the average time spent in the queue;
ρ: the server utilization; the proportion of time that a server is busy.
The term system refers to the waiting line plus the service mechanism, whilst the term queue refers to the waiting line alone.
7.4.1 Average Number of Customers in the System L
Consider a queuing system over a period of time T and let L(t) denote the number of customers in the system at time t. Let Ti be the total time in [0,T] in which the system contained exactly i customers. In general ∑∞i=0Ti=T. The average number of customers in the system is estimated by ˆL=1T∞∑i=0iTi=∞∑i=0iTiT. Notice that Ti/T is the proportion of time the system contains exactly i customers.
Let’s consider an example. Figure 7.1 gives a simulation of a queue in an interval of 20 time units. It can be seen that T0=3, T1=11, T2=5 and T3=1, and therefore ˆL=(0⋅3+1⋅11+2⋅5+3⋅1)/20=24/20=1.2 customers.
![Number in system, L(t), at time t.](images/system.jpg)
Figure 7.1: Number in system, L(t), at time t.
By looking at Figure 7.1 it can be seen that the total area under the function L(t) can be decomposed into rectangles of length Ti and height i, thus having area iTi. It follows that the total area is given by ∞∑i=0iTi=∫T0L(t)dt and therefore ˆL=1T∞∑i=0iTi=1T∫T0L(t)dt
Many queuing systems exhibit some kind of long-run stability in terms of their average performance. For such systems, as time T gets large, the observed average number of customers in the system ˆL approaches a limiting value, say L, which is called the long-run average number in system. With probability 1 we have that ˆL=1T∫T0L(t)dt→L as T→∞ If a simulation run length T is sufficiently long, the estimator ˆL becomes arbitrarily close to L.
The above equations can be applied to any subsystem of a queuing system. If LQ(t) denotes the number of customers waiting in queue, and TQi denotes the total time in [0,T] in which exactly i customers are waiting in queue, then ˆLQ=1T∞∑i=0iTQi=∫T0LQ(t)dt→LQ as T→∞
7.4.2 Average Time Spent in System per Customer w
If we simulate a queuing system for some period of time, say T, then we can record the time that each customer spends in the system during [0,T], say W1,W2,…,WN where N is the number of arrivals in [0,T]. The average time spent in system per customer, called the average system time, is given by ˆw=1NN∑i=1Wi For stable systems, as N→∞ ˆw→w with probability 1, where w is called the long-run average system time.
If the system under consideration is the queue alone, we can re-write the above equations as ˆwQ=1NN∑i=1WQi→wQ as N→∞ where WQi is the total time customer i spends waiting in queue, ˆwQ is the observed average time spend in queue (or delay) and wQ is the long-run average delay per customer.
Consider the system in Figure 7.1. It can be seen that there are 5 customers who waited W1=2, W2=5, W3=6, W4=7 and W5=4 and therefore ˆw=2+5+6+7+45=4.8 time units Thus on average these customers spent 4.8 time units in the system. As for the time spent in the queue, it can be computed as WQ1=0, WQ2=0, WQ3=3, WQ4=4 and WQ5=0, thus: ˆwQ=0+0+3+4+05=1.4 time units.
7.4.3 Little’s Law
For the example in Figure 7.1 there were N=5 arrivals in T=20 time units, and thus the observed arrival rate was ˆλ=N/T=1/4 customer per time unit. Recall that ˆL=1.2 and ˆw=4.8. Hence it follows that ˆL=ˆλˆw, since 1.2=144.8.
This relationship is not coincidental: it holds for almost all queuing systems. Allowing T→∞ and N→∞, the above expression becomes L=λw, where ˆλ→λ and λ is the long-run average arrival rate. This equality is usually called Little’s law. It says that the average number of customers in the system is equal to the average number of arrivals per time unit times the average time spent in the system. For Figure 7.1 there is one arrival every 4 minutes (on average) and each arrival spends 4.6 minutes in the system (on average), so at an arbitrary point in time there will be (1/4)(4.9)=1.2 customers present (on average).
![System times W_i for the example system.](images/system2.jpg)
Figure 7.2: System times W_i for the example system.
Little’s law can also be derived reconsidering Figure 7.1 as follows. Figure ?? shows the exact same system history, but reporting the waiting time of each customer in the system, Wi. Again we can see that the area under the function L(t) can be decomposed into rectangles of height 1 and length Wi, for each i=1,2,…,N. Therefore N∑i=1Wi=∫T0L(t)dt Therefore, by using that ˆλ=N/T we have that ˆL=1T∫T0L(t)dt=1TN∑i=1Wi=NT1NN∑i=1Wi=ˆλˆw, which is indeed Little’s law!
7.4.4 Server Utilization
Server utilization is defined as the proportion of time that a server is busy. Observed served utilization, denoted by ˆρ, is defined over a specified time interval [0,T]. Long-run server utilization is denoted by ρ. For systems that exhibit long-run stability, ˆρ→ρ as T→∞
7.4.4.1 Server Utilization in G/G/1 Queues
Consider any single-server queuing system with average arrival rate λ customers per time unit, average service time E(S)=1/μ time units, and infinite queue capacity and calling population. Notice that E(S)=1/μ implies that when busy the server is working at the rate μ customers per time unit, on average: μ is called the service rate.
Notice that the server alone is a subsystem that can be considered as a queuing system itself. hence, Little’s law L=λw can be applied to the server. For stable systems, the average arrival rate to the server, say λs must be identical to the average arrival rate to the system λ (certainly λs≤λ since customers cannot be served faster than they arrive, but if λs<λ the the waiting line would tend to grow in length and so we would have an unstable system). For the server subsystem, the average system time is w=E(S)=1/μ. The actual number of customers in the server subsystem is either zero or one as shown in Figure 7.3 for the system in Figure 7.1. Hence the average number in the server subsystem ˆLs is given by ˆLs=T−T0T In the example ˆLs=17/20=ˆρ.
![Number of customers being served at time t](images/system3.jpg)
Figure 7.3: Number of customers being served at time t
In general, for a single-server queue, the average number of customers being served at an arbitrary point in time is equal to server utilization. As T→∞, ˆLs=ˆρ→Ls=ρ. Combining these results into L=λw for the server subsystem yields ρ=λE(S)=λμ that is the long-run server utilization in a single-server queue is equal to the average arrival rate divided by the average service rate. For a single-server queue to be stable, the arrival-rate λ must be less then the service rate μ: λ<μ or ρ=λμ<1 If the arrival rate is greater than the service rate (λ>μ) the server will eventually get further and further behind. After time, the server will always be busy, and the waiting line will tend to grow in length. For stable single-server systems long-run measures of performance such as average queue length LQ are well defined and have a meaning. For unstable systems long-run server utilization is 1 and the long-run average queue length is infinite.
7.4.4.2 Server Utilization in G/G/c Queues
Consider now a queuing system with c identical servers in parallel. If an arriving customer finds more than one server idle, the customer chooses a server without favoring any particular server. Arrivals occur at rate λ from an infinite calling population and each server works at rate μ customers per time unit.
Using a similar argument as above, one can derive that long-run average server utilization is defined by ρ=λcμ and the system is stable if ρ<1 or equivalently if λ<cμ. The average number of busy servers is Ls=λμ.
7.4.4.3 An Example
Consider a doctor who schedules patients every 10 minutes and who spends Si minutes with the i-th patient, where Si={9 minutes with probability 0.912 minutes with probability 0.1 Thus, arrivals are deterministic (every 10 minutes) but services are stochastic with mean and variance given by E(Si)=9⋅0.9+12⋅0.1=9.3 minutes and V(Si)=0.9⋅(9−9.3)2+0.1⋅(12−9.3)2=0.81 minutes2 Here ρ=λ/μ=9.3/10=0.93<1 and so the system is stable and the doctor will be busy 93% of the time in the long-run. In the short-run, sometimes queues will build up temporarily because of the variability of the service distribution, as shown in Figure 7.4.
![Number of patients in the doctor's office at time t](images/system4.jpg)
Figure 7.4: Number of patients in the doctor’s office at time t