In [1]:
from mytypes import Queue

In [2]:
# A class to represent a single customer in an M/D/1 queue simulation.
# Each customer has three attributes:
#
#  - cid: A customer identifier (can be anything, but we will use consecutive integers)
#  - arrival_time: The time at which the customer arrived at the queue
#  - departure_time: The time at which the customer departed the queue
class Customer(object):
def __init__(self, cid, arrival_time):
self.cid = cid
self.arrival_time = arrival_time
self.departure_time = None

def get_wait(self):
if self.departure_time is None:
return None
else:
return self.departure_time - self.arrival_time

def __str__(self):
return "Customer({}, {})".format(self.cid, self.arrival_time)

def __repr__(self):
return str(self)

In [3]:
q = Queue()

In [4]:
q.enqueue(Customer(1, 10))

Out[4]:
True
In [5]:
q.enqueue(Customer(2, 15))

Out[5]:
True
In [6]:
q.enqueue(Customer(3, 18))

Out[6]:
True
In [7]:
q

Out[7]:
 --> Customer(3, 18) --> Customer(2, 15) --> Customer(1, 10) -->
In [10]:
import random

# simulate_md1: Simulates an M/D/1 queue.
#
# In an M/D/1 queue que have:
#
# - Arrivals follow a Markov process (M)
# - The time to service each customer is deterministic (D)
# - There is only one server (1)
#
# The function takes three parameters (plus one optional parameter)
#
# - lambd: The simulation uses an exponential distribution to determine
#          the arrival time of the next customer. This parameters is the
#          lambda parameter to an exponential distribution (specifically,
#          Python's random.expovariate)
# - mu: The rate at which customers are serviced. The larger this value is,
#       the more customers will be serviced per unit of time
# - max_time: The maximum time of the simulation
# - verbosity (optional): Can be 0 (no output), 1 (print state of the queue
#                         at each time), or 2 (same as 1, but also print when
#                         each customer arrives and departs)
#
# The function returns two lists: one with all the customers that were served
# during the simulation, and one with all the customers that were yet to be
# served when the simulation ended.
#
def simulate_md1(lambd, mu, max_time, verbosity = 0):
md1 = Queue()

# Our return values: the list of customers that have been
# served, and the list of customers that haven't been served
served_customers = []
unserved_customers = []

# The type of simulation we have implemented in this function
# is known as a "discrete event simulation"
# (https://en.wikipedia.org/wiki/Discrete_event_simulation), where
# we simulate a discrete sequence of events: customer arrivals
# and customer departures. So, we only need to keep track of when
# the next arrival and the next departure will take place (because
# nothing interesting happens between those two types of events).
# Then, in each step of the simulation, we simply advance the
# simulation clock to earliest next event. Note that, because
# we have a single server, this can be easily done with just
# two variables.

next_arrival = random.expovariate(lambd)
next_service = next_arrival + 1/mu

# We initialize the simulation's time to the earliest event:
# the next arrival time
t = next_arrival

# We will number customers starting from 1
cid = 1

while t < max_time:

# Process a new arrival
if t == next_arrival:
customer = Customer(cid, arrival_time = t)
cid += 1
md1.enqueue(customer)

if verbosity >= 2:
print("{:10.2f}: Customer {} arrives".format(t, customer.cid))

next_arrival = t + random.expovariate(lambd)

# The customer at the head of the queue has been served
if t == next_service:
done_customer = md1.dequeue()
done_customer.departure_time = t

served_customers.append(done_customer)

if verbosity >= 2:
print("{:10.2f}: Customer {} departs".format(t, done_customer.cid))

if md1.is_empty():
# The next service time will be 1/mu after the next arrival
next_service = next_arrival + 1/mu
else:
# We start serving the next customer, so the next service time
# will be 1/mu after the current time.
next_service = t + 1/mu

if verbosity >= 1:
print("{:10.2f}: {}".format(t, "#"*md1.length()))

# Advance the simulation clock to the next event
t = min(next_arrival, next_service)

# Any remaining customers in the queue haven't been served
while not md1.is_empty():
unserved_customers.append(md1.dequeue())

return served_customers, unserved_customers

In [11]:
simulate_md1(0.167, 0.15, 100, verbosity=2)

      8.44: Customer 1 arrives
8.44: #
15.11: Customer 1 departs
15.11:
20.00: Customer 2 arrives
20.00: #
26.67: Customer 2 departs
26.67:
28.55: Customer 3 arrives
28.55: #
32.11: Customer 4 arrives
32.11: ##
33.37: Customer 5 arrives
33.37: ###
33.44: Customer 6 arrives
33.44: ####
35.21: Customer 3 departs
35.21: ###
39.24: Customer 7 arrives
39.24: ####
41.85: Customer 8 arrives
41.85: #####
41.88: Customer 4 departs
41.88: ####
41.91: Customer 9 arrives
41.91: #####
48.55: Customer 5 departs
48.55: ####
50.62: Customer 10 arrives
50.62: #####
55.21: Customer 6 departs
55.21: ####
57.58: Customer 11 arrives
57.58: #####
59.45: Customer 12 arrives
59.45: ######
61.88: Customer 7 departs
61.88: #####
68.55: Customer 8 departs
68.55: ####
68.59: Customer 13 arrives
68.59: #####
68.69: Customer 14 arrives
68.69: ######
74.82: Customer 15 arrives
74.82: #######
75.21: Customer 9 departs
75.21: ######
81.88: Customer 10 departs
81.88: #####
84.16: Customer 16 arrives
84.16: ######
88.31: Customer 17 arrives
88.31: #######
88.55: Customer 11 departs
88.55: ######
91.08: Customer 18 arrives
91.08: #######
95.21: Customer 12 departs
95.21: ######

Out[11]:
([Customer(1, 8.443052843670209),
Customer(2, 19.999280377953482),
Customer(3, 28.54699008760666),
Customer(4, 32.11047866647759),
Customer(5, 33.37015203109519),
Customer(6, 33.43504747377588),
Customer(7, 39.24074388377898),
Customer(8, 41.85106883831099),
Customer(9, 41.905667317025085),
Customer(10, 50.618618009515586),
Customer(11, 57.57642944990549),
Customer(12, 59.45254067971032)],
[Customer(13, 68.59490020956505),
Customer(14, 68.68940265496177),
Customer(15, 74.82351508870018),
Customer(16, 84.16158061809296),
Customer(17, 88.31389604849224),
Customer(18, 91.08008532910335)])