Performance of Shortest Queue Discipline

We computed the performance of random line queuing discipline in the previous article. However, in real life, we don’t really throw a coin in order to pick which of the two lines we take. Most of the time, we go to the shortest line for service. Using the techniques we have learned in modeling, we will compute the performance of this queue and compare the performance to the other queueing discplines we have computed so far.

Markov Diagram

markov_shortest_line.png

As usual, the arrival rate of customers is 2 customers per minute. Each customer is given a service at an average of 20 secs, which means that an average of 3 customers are being serviced per minute.

At the start, which is state 00, there are no customers. This means that an arriving customer has 2 choices, thereby reducing the arrival rate by half. We indicate this in the figure using an orange colored arrow. The same thing happens when there are exactly 2 customers being serviced. When a new customer arrives, the arrival rate is 1 customer per minute.
We use the extremecomputing continuous markov chain solver to compute the probabilities. The input to the solver is shown below:

markov_shortest_lineinput.png

The result of the computation gives the probabilities in each state:

markov_shortest_lineresult.png

The utilization of attendant 1 is equal to 1 minus the proportion of time he/she was idle.

\displaystyle U_{\text{Attendant 1}} = 1 - P_{00} - P_{01} - P_{02}
\displaystyle = 1 - 0.501 - 0.167 - 0.0123
\displaystyle = 0.319

The throughput of the system is equal to the sum of the throughputs of both attedants:

\displaystyle X =  2*0.319*2
\displaystyle = 3.2828

customers/minute.

Comparison of Performance

It is easy to compute the throughput of each queueing discipline by adding the utilization of each attendant and multiplying the result by the arrival rate.

To compute the response time, we will use Little’s law

\displaystyle N=X\cdot R

Little’s law tells us that the response time is equal to N (the number of customers in the system) divided by the throughput. However, we still need to compute N using the probabilities computed.

The formula for computing the number of customers in the system is given by:

\displaystyle \sum_{x=0}^{3} x\cdot P(x)

where x is the number of customers.

System Throughput Response Time
Shortest Line 3.2828 0.2148
Random Line 2.8416 0.5480
Common Line 3.3208 0.2045

As can be seen in the table above, the common line system has the greatest throughput. The random line system gives the least throughput. In terms of response time, the common line also wins with the least response time of the three.

Advertisements

Published by

Bobby Corpus

Loves anything related to Mathematics, Physics, Computing and Economics.