Introduction to the M/M/1 Queue

For one of my projects, I needed to learn how to build an M/M/1 event simulator.

I thought I’d post this for everyone to see and perhaps this might help you if you’re in a Queuing Theory class.

Let’s start with an example:

You want to simulate how long it takes for people to checkout at a gas station. We assume that there is only one cashier and that anyone in the line stays in the line. The line is FIFO (First In First Out or First Come First Served). With this in mind, we’ve studied surveillance tapes and we realize that on average six people come in per hour. From monitoring register transactions, we know on average the cashier can check out eight people an hour.

There is a lot of information there. Let’s break it down and give ourselves some variables:

  1. Arrival Rate(λ): 6
  2. Service Rate(μ): 8
  3. Number of Cashiers: 1
  4. Queuing Style: FIFO

With all of these in mind, we can begin to work with our problem.

First thing that we need to assume is that arrivals and departures are exponentially distributed. How do we know this? I’ll mention it later, but you don’t even need to know what that phrase means right now.

With this information, we can decide the following information right away:

  1. Queue Utilization: λ/μ
  2. Probability that there are 0 customers in line: 1 – λ/μ
  3. Average Waiting Time: λ/(μ(μ-λ))
  4. Average Time Customer Spends in the gas station: 1 / (μ – λ)
  5. Average Number of Customers Spends waiting for service: (λ * λ) / (μ(μ-λ))
  6. Average Number of Customers in the station: (λ/μ) / (1 – (λ/μ))

Now these are all static numbers. How do we actually make a simulation?

Well, remember how we said this is a M/M/1 queue? Well the M stands for exponential distribution. So we can calculate if there is an arrival in a certain unit of time with the following equation:

Probability of arrival = λ*e^-(λ * t)

(Hopefully now the gears are starting to turn in your head on how to do this)

In this case, t stands for time. So if we want to know what is the provability of an arrival in 1 second in our above example, then we have

6 * e^-(6 * 1) = 14.87%

What is e? e stands for our Euler’s number which is the opposite of the natural log. So, ln(e) = 1. Don’t worry about that too much if you don’t get it, normally there will be a button on your calculator that puts in e for you.

If you take a random number generator and compare that with the probability of an arrival, then you can figure out if an arrival occurred.

So (in C):


float result = 100 * lambda * pow(M_E, (lambda * time)); ///M_E is our Euler's Number

odds = rand() % 100;

if(result > odds)
{
printf("Arrival occurred!\n");
}
else
{
printf("No Arrival occurred!\n");
}

Now that we’ve got arrivals, let’s handle departures.

We are going to use a very similar equation:

μ*e^-(μ * t)

See? isn’t that different at all. The trick here is that we want to keep looping until we get a departure, because otherwise our customer will be stuck in limbo and never be able to leave (and that means that no one else can leave as well).

In C:

time = 0;
while(1)
{
time++;
float result = 100 * lambda * pow(M_E, (lambda * time)); ///M_E is our Euler's Number

odds = rand() % 100;

if(result > odds)
{
break;
}
}

Here we keep looping until we get what we want.

Finally, we need to be respectful of who is in the line in front of us.

To do this, we need to have some sort of way to track when people enter the line and how long it takes for them to leave. While I did this using C++ and a vector, it could be done in C using a linked list and then finding when the last departure is. Some last bits of code are to follow.

Psudocode:

if(last_departure > arrival)
{
leave_time = last_departure - arrival + time_checking_out
}
else
{
leave_time = arrival + time_checking_out
}

Hope this makes things easier for someone else.

Code:
Click Here!

This entry was posted in Computer Science and tagged , , . Bookmark the permalink.

Leave a Reply