Systems such as factories, distribution centers, and stores that provide some kind of service to customers must function in an uncertain environment that includes probabilistic fluctuations (random customer arrivals, equipment failures, etc.). .. Therefore, when evaluating its performance, it is necessary to track how the state of the system placed in a given stochastic environment changes over time. By collecting a large number of state transition data of such a system, it becomes possible to statistically evaluate the performance of the system.
At this time, it is generally difficult to perform many experiments in a system such as an actual factory or store, so a simulation experiment using a model is effective. In particular, a technique called discrete event simulation is often used for simulation experiments of production, logistics, and service provision systems. In this article, we will understand the basics of this discrete event simulation and acquire the skills to build a simple discrete event simulation model using Python's SimPy module.
This time, as the first step to that end, we aim to understand the basic mechanism of discrete event simulation.
Simulating a system can be said to simulate how the state of the system changes over time, that is, the time evolution of the state of the system. At this time, in the discrete event simulation, it is considered that the state of the target system changes (only) when some event occurs. This way of thinking about state changes is the basic feature of discrete event simulation.
Therefore, when executing a discrete event simulation,
Must be clearly defined. Specifically, these are determined according to what kind of system is targeted, what aspect of the system is of interest, and so on. It can be said that modeling for discrete event simulation is to set these appropriately and clearly.
The timing of occurrence of a stochastic event is often modeled by considering the occurrence interval of the event as a random variable and specifying its distribution. For example, remember that the intervals between randomly occurring events follow an exponential distribution. In addition, the event that some activity including uncertainty in the duration ends is when the distribution of the duration of the activity is modeled by, for example, a normal distribution, and a random number that follows the distribution of the duration is added to the start time. It would be good to set it so that it occurs in.
The most basic way to implement the discrete event simulation function is to have a list of events arranged in ascending order of their occurrence timing, take out the events one by one from the beginning, and generate them in sequence. Is. This list is called an event calendar. Each time an event is retrieved from the event calendar, the simulation time is advanced to the timing at which the event occurs. Then, the values of the variables representing the system state are updated according to the rules that describe how the system state changes when the event occurs.
Now let's look at a (very simple) implementation of the event and event calendar.
class Event:
def __init__(self, time, kind):
self.time = time # when this event occurs
self.kind = kind # the type of this event
def __str__(self):
return self.kind
class Calendar:
def __init__(self, horizon):
self.queue = [Event(horizon, 'end')] # list of events
def append(self, e): # add a new event to the list
self.queue.append(e)
self.queue.sort(key=lambda x: x.time) # sort events chronologically
def trigger(self): # trigger the first event in the list
e = self.queue.pop(0)
return e
Event is a class of events. For the time being, this class has two pieces of information, the time of occurrence (time) and the event type (kind). If necessary, you can add other parameters as well.
Calendar is a class of event calendars. There is a list named queue, to which one event of the type end (end event) is added. This is an event to end the simulation, and the length of the simulation period should be passed to the argument horizon, which indicates the timing of its occurrence, when the instance is created. ʻAppend (e) is a method that adds a new event ʻe to the calendar. After adding the event ʻe to the list queue`, it can be seen that the events are sorted in ascending order of occurrence timing.
trigger () is a method for fetching the first event in the list queue. In this case, the event is simply extracted from the list and return is performed, and various processes associated with the occurrence of the event need to be implemented separately. Also, for the sake of simplicity, exception handling when queue is empty is omitted.
In addition, I explained above that the event calendar is a list, and even in this implementation example, it is actually implemented as a list, but of course, if events can be stored and can be retrieved one by one in the order of occurrence timing, heap etc. ， Other data structures may be used.
Next, let's get an image of mounting the main body of the simulation model using these parts. As an example, a simple skeleton is shown.
import random
class Skelton:
def __init__(self, horizon):
self.now = 0 # simulation time
self.cal = Calendar(horizon) # event calendar
self.add_some_event() # an initial event is added
self.count = 0 # an example state variable (the number of events triggered)
def add_event(self, dt, kind):
e = Event(self.now +dt, kind)
self.cal.append(e)
def add_some_event(self):
self.add_event(random.expovariate(1), 'some_event')
def print_state(self):
print('{} th event occurs at {}'.format(self.count, round(self.now)))
def run(self):
while True:
self.print_state()
e = self.cal.trigger()
print(e)
self.now = e.time # advance the simulation time
self.count += 1 # increment the event counter
if e.kind == 'end': # time is up
break
else:
self.add_some_event() # next event is added
Skelton is a class of simulation model (skeleton) of the target system. The simulation time is managed by the variable now (initial value is 0) in it. Also, it can be seen that cal is an instance of the event calendar and is generated by inheriting the argument horizon passed at the time of model generation. count is a dummy of the system state variable, which counts the number of occurrences of an event. When implementing a practical model, it is a good idea to replace it with the necessary state variables.
ʻAdd_event () is a method that takes the time and type until the occurrence time as arguments and adds the new event to the event calendar. We also define a method ʻadd_some_event () that adds one dummy event of the type some_event given by a random number that follows an exponential distribution with a time to occurrence. priint_state () is a method that writes the system state to the console.
The final run () is the method for running the simulation. In the while loop, we can see that the system state is first written out, then the event is taken out from the event calendar, the type of the event is written out, the simulation time is advanced, and the number of occurrences of the event count is incremented. If the event that occurred is end, the simulation ends through the while loop, but if not, a new some_event event is added to the event calendar and the next loop is advanced.
Let's actually move this (skeleton) simulation model. To do this, first create an instance and then execute it with the run () method (don't forget to execute the code of the Event class, Calendar class, and Model class above). Things to keep).
model = Skelton(200)
model.run()
It can be seen that events occur one by one at random, and the simulation time progresses accordingly. This simple flow is the basic structure of the discrete event simulation algorithm, so let's keep it in mind here.
Next, let's flesh out the above skeleton a little and make one concrete simulation model (which is very simple). Let's model a situation in which a customer randomly visits a store that manages the inventory of a certain item by a fixed-quantity ordering method and purchases the item. It is assumed that the customer purchases one item if it is in stock at the store when he / she comes to the store and returns, and if it is out of stock, an opportunity loss occurs. Also, assume that the average arrival interval of customers is 1.
We will define the Model class by using the Event class and Calendar class as they are, inheriting the Skelton class, and fleshing out a little according to this concrete example. The code below is an example.
class Model(Skelton):
def __init__(self, horizon, op, oq, lt, init):
self.now = 0 # simulation time
self.cal = Calendar(horizon) # event calendar
self.add_arrival() # an arrival event is added
self.op = op # ordering point
self.oq = oq # order quantity
self.lt = lt # replenishment lead time
self.at_hand = init # how many items you have at hand
self.loss = 0 # opportunity loss
self.orders = [] # list of back orders
@property
def total(self): # total inventory level including back orders
return sum(self.orders) +self.at_hand
def add_arrival(self): # arrival of a customer
self.add_event(random.expovariate(1), 'arrival')
def add_fill_up(self): # replenishment of ordered items
self.add_event(self.lt, 'fill_up')
def sell_or_apologize(self):
if self.at_hand > 0:
self.at_hand -= 1 # an item is sold
else:
self.loss += 1 # sorry we are out of stock
def fill_up(self): # receive the first order in the list
if len(self.orders) > 0:
self.at_hand += self.orders.pop(0)
def stocktake(self):
if self.total <= self.op:
self.orders.append(self.oq)
return True # ordered
return False # not ordered
def print_state(self):
print('[{}] current level: {}, back order: {}, lost sales: {} '.format(round(self.now), self.at_hand, self.orders, self.loss))
def run(self):
while True:
self.print_state()
e = self.cal.trigger()
print(e)
self.now = e.time # advance the simulation time
if e.kind == 'end': # time is up
break
elif e.kind == 'fill_up':
self.fill_up()
elif e.kind == 'arrival':
self.sell_or_apologize()
self.add_arrival()
ordered = self.stocktake()
if ordered:
self.add_fill_up()
In addition to the simulation period (horizon), the order point (ʻop), order quantity (ʻoq), replenishment lead time (lt), and initial stock quantity are specified as arguments when creating an instance of the simulation model. Four (ʻinit) have been added. In addition, the state variable count has been deleted and replaced with a list of over-the-counter inventory (ʻat_hand), opportunity loss occurrences (loss), and unreplenished orders (backorders) (ʻorders`). Has been done. In addition, it can be seen that one arrival event is added to the event calendar at the beginning. This is an event corresponding to the first customer's visit.
Looking at the methods, we can see that ʻadd_arrival () and ʻadd_fill_up () play a role in adding new arrival and fill_up events to the event calendar, respectively. sell_or_apologize () describes how to deal with customers who come to the store (sell one if in stock, add one opportunity loss if not). On the other hand, fill_up () is a method corresponding to filling. stocktake () checks the inventory level (total including back order), decides whether to place an order according to the rules of the fixed quantity ordering method, and orders a predetermined quantity if necessary. It corresponds.
In the run () method, the processing when an event occurs is slightly changed according to the target system this time. Specifically, if the event that occurred is a fill_up event, the fill_up () method is simply called. If it is an arrival event, perform customer support (sell_or_apologize () method), add the next arrivall event to the event calendar, and then check the inventory level and determine the order (stocktake () method). You can see that there is. If an order is placed here, the fill_up event corresponding to the order is added to the event calendar.
For example, run this model with simulation period horizon = 200, order point ʻop = 10, order quantity ʻoq = 20, replenishment lead time lt = 10, and initial stock quantity ʻinit = 20`. To see it, execute the code below.
model = Model(200, 10, 20, 10, 20) # horizon, op, oq, lt, init
model.run()
Since it is difficult to understand if the simulation results simply flow on the screen as character strings, consider displaying them in a graph. To that end, let's first introduce a simple log class. This kind of class will also be useful when you want to write the simulation results to a csv file or the like.
class Log:
def __init__(self):
self.time = []
self.at_hand = []
self.loss = []
self.total = []
def extend(self, model):
self.time.append(model.now)
self.at_hand.append(model.at_hand)
self.loss.append(model.loss)
self.total.append(model.total)
def plot_log(self):
plt.plot(self.time, self.at_hand, drawstyle = "steps-post")
plt.xlabel("time (minute)")
plt.ylabel("number of items")
plt.show()
For the time being, for each time when the event occurs, the values of the over-the-counter inventory amount (ʻat_hand), the number of opportunity loss occurrences (loss), and the total inventory level (total) at that time are stored in the log. I will go. Prepare a list to store the values of each of these variables, and implement the ʻextend (model) method to add the values of each variable of model at that time to the corresponding list. You can see that there is. The plot_log () method is a method for displaying the result as a line graph, but details are omitted here.
Let's add this to the model created above. I added only 3 lines, but the modified Model4Plot class is shown below (it inherits the Model class above, and the added 3 lines have a comment to clarify it).
class Model4Plot(Model):
def __init__(self, horizon, op, oq, lt, init):
super().__init__(horizon, op, oq, lt, init)
self.log = Log() # <-- added
self.log.extend(self) # <-- added
def run(self):
while True:
self.print_state()
self.log.extend(self) # <-- added
e = self.cal.trigger()
print(e)
self.now = e.time
if e.kind == 'end':
break
elif e.kind == 'fill_up':
self.fill_up()
elif e.kind == 'arrival':
self.sell_or_apologize()
self.add_arrival()
ordered = self.stocktake()
if ordered:
self.add_fill_up()
With this, the state of the system during the simulation will be saved in the log (model.log) in sequence. As a result, after executing the simulation, it became possible to use this data to display the transition of the in-store inventory in a line graph, for example, with the following code.
import matplotlib.pyplot as plt
model = Model4Plot(200, 10, 20, 10, 20) # horizon, op, oq, lt, init
model.run()
model.log.plot_log()
Finally, let's try to make a simple system simulation model based on the skeleton introduced above. The target of this time is the following system.
= cap).= ub), the customer will not line up in the column and will give up and return (loss of opportunity will occur).= mt, variance = vt).This time, we introduced the basic mechanism of discrete event simulation and its simple implementation example. As mentioned in "Introduction", I would like to introduce the SimPy module (which did not appear this time) from the next time.
Recommended Posts