In [3]:
from mytypes import Queue

In [4]:
# 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):
CUSTOMER_ID = 0

def __init__(self, arrival_time):
Customer.CUSTOMER_ID += 1
self.cid = Customer.CUSTOMER_ID
self.arrival_time = arrival_time
self.departure_time = None

@property
def 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 [6]:
q = Queue()

In [7]:
q.enqueue(Customer(10))

Out[7]:
True
In [8]:
q.enqueue(Customer(15))

Out[8]:
True
In [9]:
q.enqueue(Customer(18))

Out[9]:
True
In [10]:
q

Out[10]:
 --> Customer(3, 18) --> Customer(2, 15) --> Customer(1, 10) -->
In [13]:
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

while t < max_time:

# Process a new arrival
if t == next_arrival:
customer = Customer(arrival_time = t)
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 [15]:
simulate_md1(0.167, 0.15, 100, verbosity=2)

      9.97: Customer 18 arrives
9.97: #
11.39: Customer 19 arrives
11.39: ##
16.63: Customer 18 departs
16.63: #
17.88: Customer 20 arrives
17.88: ##
23.30: Customer 19 departs
23.30: #
25.43: Customer 21 arrives
25.43: ##
26.00: Customer 22 arrives
26.00: ###
29.97: Customer 20 departs
29.97: ##
32.10: Customer 23 arrives
32.10: ###
32.76: Customer 24 arrives
32.76: ####
36.27: Customer 25 arrives
36.27: #####
36.63: Customer 21 departs
36.63: ####
43.30: Customer 22 departs
43.30: ###
46.73: Customer 26 arrives
46.73: ####
49.97: Customer 23 departs
49.97: ###
56.63: Customer 24 departs
56.63: ##
59.03: Customer 27 arrives
59.03: ###
63.30: Customer 25 departs
63.30: ##
67.99: Customer 28 arrives
67.99: ###
69.97: Customer 26 departs
69.97: ##
71.91: Customer 29 arrives
71.91: ###
74.22: Customer 30 arrives
74.22: ####
76.63: Customer 27 departs
76.63: ###
83.30: Customer 28 departs
83.30: ##
83.92: Customer 31 arrives
83.92: ###
89.45: Customer 32 arrives
89.45: ####
89.97: Customer 29 departs
89.97: ###
90.81: Customer 33 arrives
90.81: ####
96.63: Customer 30 departs
96.63: ###

Out[15]:
([Customer(18, 9.965045551815654),
Customer(19, 11.389394379247163),
Customer(20, 17.875821656819195),
Customer(21, 25.426495937576668),
Customer(22, 26.00475868339236),
Customer(23, 32.10423589418061),
Customer(24, 32.756571150142626),
Customer(25, 36.26807555744685),
Customer(26, 46.73055590465614),
Customer(27, 59.034085256547094),
Customer(28, 67.98773129899615),
Customer(29, 71.90856444455392),
Customer(30, 74.22451939114713)],
[Customer(31, 83.92182575854864),
Customer(32, 89.45002565630345),
Customer(33, 90.80617743490446)])