from mytypes import Queue
# 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)
q = Queue()
q.enqueue(Customer(1, 10))
True
q.enqueue(Customer(2, 15))
True
q.enqueue(Customer(3, 18))
True
q
--> Customer(3, 18) --> Customer(2, 15) --> Customer(1, 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
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: ######
([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)])