Computing Continuous Markov Chains Using Extreme Optimal Solver

In the last article, we computed the probabilities associated with the states in a continuous markov chain model using balance equations. The computation, although elementary, was tedious and distracts us from the real problem, which is understanding the performance of a queueing model. Fortunately, there is an online tool we can use in order to speed up the computation of continuous markov chains. This tool can be found in the site http://www.extremecomputing.org. This site contains numerous solvers that can be of interest to the computational scientists. However, the tool we are interested in is the Continuous Markov Chain solver which can be accessed in this link.

When you click on the link above, you will be seeing a text box with a default input, as shown in the image below.

open_solver1.png

The input to this solver is a tabular data consisting of three columns. The first two columns correspond to state transitions. The first column is the beginning state of the system. The second column is the state to which the system will make a transition. The input to these columns are identifiers that correspond to the label of the state. The third column is the rate of the transition and should be a numeric type.

Example 1
The solver page has an example which we can use to illustrate how to use this tool. The first row of the example means that when the system is in state 0, it can do a state transition to state 1 at rate 2. The same goes with the other rows of this input. All possible state transitions should be enumerated in this table in order to get the correct answer.

Example 2

Let us now use this tool to analyze the performance of a two-server queueing system. We will extend the ice cream stand analogy to two attendants. Suppose business is doing well and the number of customers have doubled. We realized that we can make more money by selling more ice creams in a day. So we hired another attendant that can serve ice cream as fast as the first person. Suppose that the buffer length is still 3, which means that if a prospective customer sees that the total number of persons being served and waiting in line is 3, that customer go away and instead will buy ice cream from the competitor. Now when a customer decides to buy ice cream from the store, he/she will decide in which attendant to line up. In this example, we assume that the customer picks a line at random. What is the performance of this system?

Modeling the system

The markov chain diagram of this two-server system with random-line queueing discipline is shown below:

markov_random_line_fig.png

Blue arrows represent customers arriving to buy ice cream. Red arrows represent customers leaving after being served with ice cream. Let us assume that the rate at which customers arrive is 2 per minute and the rate at which our attendants serve a customer is 20 seconds per customer.

In the figure, we can see that when the system is at state 00, it can transition to states 01 and 10. It transitions to state 01 at the rate 2 customers/minute. It transitions to state 10 at the same rate.

When the system is in state 01, it can transition to state 02 at 2 customers/min, to state 11 at 2 customers/min, to state 00 at 1/3 customers/min.

Tabulating all of these state transitions and their corresponding rates result in the following table:

markov_random_line_input.png

Entering these values into the text box

markov_random_line_input2.png

and pressing submit, we get the following results:

markov_random_line_results.png

System Performance

From this result, we can immediately compute for the throughput of attendant 1 and attendant 2. The utilization of attendant 1 is equal to 1 minus the sum of the percentage of time it was idle.
\displaystyle U_{\text{attendant 1} } = 1-P_{00} - P_{01} - P_{02} - P_{03}
\displaystyle =0.7370716

In the same way, the utilization of attendant 2 is

\displaystyle U_{\text{attendant 2}}= 1-P_{00} - P{10} - P_{20}-P_{30}
\displaystyle =0.7370716

We obseve that the two attendants have the same utilization. From the Utilization Law, the throughput of attendant 1 is :

\displaystyle X_{\text{attendant 1}} =  U_{\text{attendant 1}}/S_{\text{attendant 1}}
\displaystyle = 0.7370716/0.333
\displaystyle = 2.213428

The system throughput is the sum of the throughput of both attendants, which is equal to

\displaystyle X_{\text{system}} = X_{\text{attendant 1}} + X_{\text{attendant 2}}
\displaystyle = 4.426856

customers/minute.

In the next article, we are going to analyze two more queueing disciplines namely:

  • customers select the shortest line to queue.
  • there is only one line and customers go to the next available attendant.

We are going to compare them according to response time and throughput and see which queueing discipline is best for a given objective.

Advertisements

Published by

Bobby Corpus

Is an IT Architect.