Archive for December, 2006

  |  
December 10, 2006

Modeling Queuing Systems Using Markov Chains

by Bobby Corpus

Have you ever notice how various establishments make people line in a certain way? Have you gone to a bank and noticed a number of tellers servicing each client but there is only one line? Wouldn’t it be more natural to let people line up before each teller like you see in a grocery? The way customers are lined up in a server or system of servers is called Queueing Discipline.
In this article, we will learn how various queuing disciplines will affect the values of the performance metrics. We will use continuous markov chain analysis that we learned in the last article.

Motivating Scenario

Assume that the counter of a certain fast food store is arrange in a 2-stage way. The customers first place their order in counter 1, pays the cashier and proceeds to counter 2 to wait for their order to be picked up. Let a be the rate at which customers arrive, b the rate at which customers places their order and also the rate at which they leave the second counter. Let us draw the markov chain diagram of this system.

Each state is described by two numbers. The first number refers to the number of customers in the first counter. The second number refers to the number of customers waiting at the second counter. For example, state 00 mean that there are no customers being serviced. State “12″ mean that one customer is in counter 1 and 2 customers in counter 2. The blue arrows represent arrivals at rate a and red arrows are represent the rate of customers going to counter 2 and those leaving the counter 2.

markov1.png

Let us examine the four states in the diagram below. There is a blue arrow from state “00″ to state “10″ because when the first customer arrives, the first station will have 1 customer but no one in line yet in counter 2. This means that when the first customer arrives, the system will be in state “10″. There is an arrow from state “10″ to “01″. The means that the first customer is already in counter 2 to pickup his/her order but no new customer has arrived yet. There is a red arrow from state “01″ to “00″. This means that the single customer has already picked up his/her food and has left leaving the system with no customers at both stations. Notice that there is no arrow from state “10″ to “00″ because the customer who is in counter 1 cannot just leave the system but has to go to counter 2 before leaving.

markov2.png
Balance Equations
Now that we have understood why the arrows point from one state to the next, we now setup the balance equations. At steady state, the sum of flows going to one state must equal the sum of flows going out of that state. By definition, the flow along an arrow is equal to the rate along the arrow multiplied by the probability of the system being in the current state.Let us do the balance equation for state “00″. There is one arrow going to state “00″ and one arrow going out of state “00″. Therefore the flow going to state “00″ is equal to the rate going from state “01″ to “00″ multiplied by the probability of the system being in state “01″ : bP_{01}. This is equal to the flow going out of state “00″ to state “10″: a*P00. Therefore,we have,

\displaystyle a P_{00} = bP_{01}

Let us now compute the balance equation for state “01″. As you can see, there are 2 arrows out of state “01″ and one arrow going into state “01″. The balance equation is therefore:

a P_{01} + b P_{01} = b P_{10}

Doing this for all states, we get the following balance equations:

\displaystyle aP_{02} + bP_{02} = b P_{11} + b P_{03}
\displaystyle b P_{03} = bP_{12}
\displaystyle aP_{00} + bP_{11} = bP_{10} + aP_{10}
\displaystyle aP_{01} + bP_{12} + bP_{20} = bP_{11} + bP_{11} + aP_{11}
\displaystyle bP_{12} + bP_{12} = aP_{02} + bP_{21}
\displaystyle bP_{20} + aP_{20} = aP_{10} + bP_{21}
\displaystyle bP_{21} + bP_{21} = aP_{11} + bP_{30}
\displaystyle b P_{30} = a P_{20}

We add to these equations the condition that the sum of all probabilities is equal to 1:

\displaystyle P_{00} + P_{01} + P_{02} + P_{03} + P_{10} + P_{11} + P_{12} + P_{20} + P_{21} + P_{30} = 1

Solving for the probabilities using elementary algebra, we get the following:

\displaystyle P_{01} =\frac{ab^2}{b^3+2ab^2+3a^2b + 4a^3}
\displaystyle P_{02} =\frac{a^2b}{b^3+2ab^2+3a^2b + 4a^3}
\displaystyle P_{03} =\frac{a^3}{b^3+2ab^2+3a^2b + 4a^3}
\displaystyle P_{10} =P_{01}
\displaystyle P_{11} =P_{02}
\displaystyle P_{12} =P_{03}
\displaystyle P_{20} =P_{02}
\displaystyle P_{21} =P_{03}
\displaystyle P_{03} =P_{30}
\displaystyle P_{00} =(b/a)P_{01}

A simple Example

Suppose that customers arrive on the average of 1 customer per minute and can place and pay for their order in 2 minutes. After that they wait on the average of 2 minutes at the second counter to take out their order. Using the formula above, we have a = 1 and b=2. We can now solve for the probabilities by substituting these values to the above formula.

\displaystyle P_{01} = \frac{ab^2}{b^3+2ab^2+3a^2b + 4a^3} = \frac{1\cdot 2^2}{1^3+ 2\cdot 1\cdot 2^2 + 3\cdot 1^2\cdot 2 + 4\cdot 1^3}
\displaystyle =\frac{2}{13}

Computing the rest of the values, we get the following table:

P00 4/13
P01,P10 2/13
P02,P11,P20 1/13
P03,P12,P21,P30 1/26

We can compute for the Utilization of the first counter by using it’s idle time. Notice that the first counter does not have anything to do when there are no customers lining in front of it. This happens in states P00, P01, P02 and P03. Notice that these states have the first number equal to 0 (which means: no customer in that counter). Therefore, the utilization is equal to 1 minus the idle time of counter 1, i.e,

\displaystyle U_\text{counter 1} = 1 - P_{00} - P_{01} - P_{02} - P_{03}
\displaystyle =\frac{11}{26}

Using the Utilization law we learned in a previous article, we can compute the throughput of counter 1 to be:

\displaystyle X_\text{counter 1} = \frac{U_\text{counter 1}}{S_\text{counter 1}}
\displaystyle =\frac{11/26}{2}
\displaystyle =\frac{11}{52}

This happens to be the system throughput also since each customer will visit a counter only once per transaction.

Now that we know how to model using markov chains, in the next article, we will analyze other queueing disciplines and compare them according to throughput and response time.

Posted in Performance | Comments Off

  |  
Follow

Get every new post delivered to your Inbox.