Modelling Resources and Queues in Simpy

The Coffee Machine

What was described in my previous post with the clock was an example of a process. In this post we will discuss resources – the second key component of making discrete-event simulations. If a process is a series of actions or events, a resource is something of value which processes interact with.

 

Requesting, Seizing and Releasing a Resource

For example a communal coffee machine at an office is a resource. It is defined in SimPy as:

coffee_machine = simpy.Resource(env, capacity=1)

When a person walks to the kitchen to make coffee they need to use the coffee machine, and will do so if it is free. This is called requesting a resource.

Screen Shot 2017-09-25 at 22.24.47

Requesting a resource is defined in SimPy with two lines of code:

request = coffee_machine.request()
yield request

The basic resource has a capacity assigned to it, the capacity value represents the number of times the resource can be seized before it is no longer available.You can think of capacity as the number of users which can use the kettle simultaneously – in this case I am going to assume that this is a very simple coffee machine with a capacity of 1. If there is spare capacity, in this case if nobody else if using the coffee machine, then the resource is taken and the amount of spare capacity decreases by one. This is called seizing a resource.

A resource itself operates like this:

Screen Shot 2017-09-25 at 22.26.48

What this means is that if the coffee machine is not free, then the program waits until it becomes free. This means that the process waiting for the coffee machine joins a queue. Queues are a fundamental concept of discrete-event simulation.

This coffee machine is set up as a first-come-first-serve resource, which is the default resource type in SimPy. This means that if there is a queue, the person who is at the front of that queue (i.e. has been there the longest) gets access to the resource. There are a number of other resource types in SimPy, but more on these later.

After the person has made their coffee using the machine, they will let the next person use it. This is called releasing the resource. The release has to be explicitly defined in Python as follows:

coffee_macine.release(request)

There is a method to automatically release resources automatically when you are done using them. This is by defining the resource within a with statement like this:

with coffee_machine.request() as request:
	yield request

When the with statement is used the resource is automatically released when the exiting the with. This has the advantage of requiring less code to write as well as ensuring that your resources are released. However in general I do not recommend using it as you will be giving yourself less control over when to release the resource, which will be very important with more complex simulations. For the purposes of the coffee machine simulation, we will stick with explicitly defining when to release the resource.

The final logic for our coffee machine therefore looks like this:

Screen Shot 2017-09-25 at 22.27.34

Notice that we don’t explicitly define the seizing of the resource.This is because when visually modelling, it is implicit that the resource is seized if the process passes the resource request.

 

Triangular Distribution

Now onto writing this up in code form. I am going to assume that walking to the kitchen and making coffee are both random variables and follow a triangular distribution. The triangular distribution is incredibly useful in the real word as it is easy to gather data from people to fit the distribution.

Many people assume that you need to use a normal distribution for random variables. Try asking people what the standard deviation of the amount of time it takes them to make a cup of coffee is and get back to me.

The triangular distribution is thus useful because it is simple. An even simpler distribution to use is the uniform distribution, which only defines a minimum and a maximum. This is very useful if you have very little information on the process you are trying to model. Since we can make some good guesses about how long it takes to walk to the coffee machine and make coffee we will stick with the triangular.

The triangular distribution is defined by three parameters: the minimum, the maximum and the median (the middle). When gathering data from people to sue as input to your simulations, it is very helpful to be able to define these three parameters.

The triangular distribution looks like when when plotted.

Screen Shot 2017-09-25 at 22.57.37

Sampling from a triangular distribution can be defined in Python with the random module from numpy as such:

# import the random component of numpy
from numpy import random

# define the triangular distribution
def triangular_distribution(minimum, maximum, median):
    x = random.triangular(minimum, median, maximum)
    return x

 

Building the First Model

There are two events that need times defined for them in our model; walking to the kitchen and making a cup of coffee. It is good practice to define the data that you are going to use inside a table. We are going to assume that everything is in seconds in this simulation.

Event Minimum Time (s) Maximum Time (s) Most Likely Time (s)
Walk to kitchen 10 30 20
Make coffee 30 120 45

Putting the event times into the model we end up with the following code. You will see print statements added, this makes following the output of the code easier.

# import the module simpy
import simpy
# import the random component of numpy
from numpy import random

# define the triangular distribution
def triangular_distribution(minimum, maximum, median):
    x = random.triangular(minimum, median, maximum)
    return x    

# describe the process
def get_a_coffee(env, coffee_machine):
    # walk to kitchen
    print('%ds - Walking to kitchen' % env.now)
    yield env.timeout(triangular_distribution(10, 30, 20))
    print('%ds - Arrived at kitchen' % env.now)

    # request coffee machine
    print('%ds - Requesting use of coffee machine' % env.now)
    request = coffee_machine.request()
    yield request
    print('%ds - Seized coffee machine' % env.now)

    # make coffee
    print('%ds - Making coffee' % env.now)
    yield env.timeout(triangular_distribution(30, 120, 45))
    print('%ds - Finished making coffee' % env.now)

    # relese coffee machine for next person
    print('%ds - Releasing coffee machine' % env.now)
    coffee_machine.release(request)

# create the simpy environment
env = simpy.Environment()

# define the resources
coffee_machine = simpy.Resource(env, capacity=1)

# start the process
env.process(get_a_coffee(env, coffee_machine))

# run the process until time = 2
env.run(until = 100)

Output:

0s - Walking to kitchen
13s - Arrived at kitchen
13s - Requesting use of coffee machine
13s - Seized coffee machine
13s - Making coffee
54s - Finished making coffee
54s - Releasing coffee machine

Now, this isn’t very exciting as we only have one person going to make a cup of coffee. What happens if we have two people going to make coffee. We need to expand the simulation with something called a source.

 

The Source

Screen Shot 2017-09-25 at 22.59.23

In The Matrix the source is the central computing core that controls all of the machines. Our simulation source has nothing to do with The Matrix, but the source is similar in that it is responsible for generating all processes that then go off and do their own thing.

For our coffee machine simulation, we will want to create a source that can generate people. We want to randomly send people to the kitchen to make some coffee and keep doing this until the simulation ends.

 

The Exponential Distribution

Random arrivals are generally well modelled using what is known as an exponential distribution. When you are waiting to cross the road, the frequency of cars generally follows this distribution. It is useful in tat it can be defined by a single parameter, the mean (average) time.

A function can be written in Python as follows to sample from the exponential distribution:

# import the random component of numpy
from numpy import random

# define the exponential distribution
def exponential_distribution(mean):
    s = 1.0 / mean
    x = random.exponential(s)
    return x

 

Coding the Source

Now that we have a way of sampling from the exponential distribution, it is possible to define the code that will create people wishing to make coffee. We will assume that this is the morning, when everyone is arriving at work, so every 60 seconds on average a person will want to make a cup of coffee.

Here’s what a working model, simulating the coffee making in the office for a five minute period during the morning peak looks like. I’ve added in a probe to measure how long the queue time for each person is.

# import the module simpy
import simpy
# import the random component of numpy
from numpy import random

# define the exponential distribution
def exponential_distribution(mean):
    x = random.exponential(mean)
    return x

# define the triangular distribution
def triangular_distribution(minimum, maximum, median):
    x = random.triangular(minimum, median, maximum)
    return x    

# define the source
def source(env):
    i = 1
    while True:
        # start the process
        t = exponential_distribution(60)
        yield env.timeout(t)
        env.process(get_a_coffee(env, coffee_machine, i))
        i += 1

# describe the process
def get_a_coffee(env, coffee_machine, name):
    # walk to kitchen
    print('%ds - Person %d walking to kitchen' % (env.now, name))
    t = triangular_distribution(10, 30, 20)
    yield env.timeout(t)
    print('%ds - Person %d arrived at kitchen' % (env.now, name))

    # request coffee machine
    print('%ds - Person %d requesting use of coffee machine' % (env.now, name))
    request = coffee_machine.request()
    yield request
    print('%ds - Person %d seized coffee machine' % (env.now, name))

    # make coffee
    print('%ds - Person %d making coffee' % (env.now, name))
    t = triangular_distribution(30, 120, 45)
    yield env.timeout(t)
    print('%ds - Person %d finished making coffee' % (env.now, name))

    # relese coffee machine for next person
    print('%ds - Person %d releasing coffee machine' % (env.now, name))
    coffee_machine.release(request)

# create the simpy environment
env = simpy.Environment()

# define the resources
coffee_machine = simpy.Resource(env, capacity=1)

# start the source process
env.process(source(env))

# run the process
env.run(until = 300)

Running this code gives us an output that will look something like the following, although every time you run the simulation you should get a slightly different result as we are using random variables.

20s - Person 1 walking to kitchen
28s - Person 2 walking to kitchen
43s - Person 2 arrived at kitchen
43s - Person 2 requesting use of coffee machine
43s - Person 2 seized coffee machine
43s - Person 2 making coffee
44s - Person 1 arrived at kitchen
44s - Person 1 requesting use of coffee machine
121s - Person 2 finished making coffee
121s - Person 2 releasing coffee machine
121s - Person 1 seized coffee machine
121s - Person 1 making coffee
121s - Person 3 walking to kitchen
144s - Person 3 arrived at kitchen
144s - Person 3 requesting use of coffee machine
145s - Person 4 walking to kitchen
162s - Person 4 arrived at kitchen
162s - Person 4 requesting use of coffee machine
166s - Person 1 finished making coffee
166s - Person 1 releasing coffee machine
166s - Person 3 seized coffee machine
166s - Person 3 making coffee
219s - Person 3 finished making coffee
219s - Person 3 releasing coffee machine
219s - Person 4 seized coffee machine
219s - Person 4 making coffee

Average queue time in this simulation was: 39s

Just from reading the output you can see the interactions between processes and the coffee machine resource. It’s interesting to see person 1 is the first person to walk to the kitchen, but person 2 actually gets there first. At the 43s mark, person 2 who has arrived at the kitchen quickly and really wants coffee, seized the coffee machine Person 1 arrives at the kitchen one second later at 44s, but cannot use the machine because person 2 has started using it! At 121s we can see person 2 giving up their use of the coffee machine, at which point person 1 immediately seizes it. However this means that person 1 had to wait 77s in the kitchen until they could start making their coffee!

Here is how long each person had to queue in the kitchen for their coffee.

Screen Shot 2017-09-25 at 23.01.02

You can produce a vast range of useful simulations with no further knowledge than knowing how to create processes and resources.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s