Discrete Event Simulation

Introduction to discrete event simulation

Model of a Supermarket

“Customers come by car –which they park at the parking lot- or on foot to the customer (see figure below). They shop for a certain average time, some of them visit the butcher, others the infodesk. Then they choose a pay desk, wait their turn, pay and leave the supermarket.”

Suppose we want to study how much time customers spent at the supermarket. Discrete event simulation is an ideal method for this.
We start by creating a model of the supermarket

Model

Modeling is dividing the system into logical processes (abbreviation lp), which are connected by channels. This forms the static part or topology of the model (see figure below). The dynamics of the system are then described by the events, which travel through the channels between the logical processes.

The town generates car and customer events, it serves as a source, and also as a sink: outgoing car and customer events terminate there. The entrance lp is what we call in simulation language a multiplexer (mux), it brings together several channels into one. The floor lp is modelled as a so-called delay (namely the shopping time) and it also distributes customers to the butcher and info queue. The butcher and info-desk are what we call queues: events come in, are queued and processed one by one (according to the first-in first-out priciple). The pay-desks are also queues, but are more specific: they can be turned off, the cashier leaves the pay-desk when the number of waiting customers is low. This information is send to the desk-select process, where the customers are distributed to queues of the pay-desks. This is what we call a demultiplexer (demux): one channel is broken down in multiple channels. Also the exit lp is a demultiplexer: customers with a car are sent to the parking lot, customers on foot leave the supermarket immediately.

So, what is discrete event simulation? It is the processing of the events by the logical processes and the travelling of the events along the channels. At a certain time, there will be many events spread out in the model, each with a certain timestamp, indicating at what time it arrives in the next lp and will be processed there according to the lp’s behaviour. This is what we call event-driven simulation: the systems dynamics are triggered by events.

Remarks
The modeler has to choose a certain level of detail or level of abstraction. We can go more into detail, by decomposing the floor lp into detailed processes. Or we can go less into detail by leaving out the parking process and/or the butcher and info queue. This depends on what dynamics you want to study and what is important in that study.

All simulation is triggered by events: no event, no change. That’s why we have to add a feedback trigger channel to the town lp (see figure). As explained, the town serves as a source, so it generates events. However, to do this it should receive an event! This chicken & egg problem is solved with a feedback channel: a trigger event comes in along the feedback channel, the lp generates a car event, but also sends back the trigger event to the feedback channel to indicate the next time an event will be generated.

In the supermarket model, there are 4 types of events: trigger, car, customer and pay-desk info.

Sources, sinks, multiplexers, demultiplexers, queues are basic lp’s, they are found in many models (see figure).

Implementation

3 things should be implemented:

(1) The initial events.
The simulation starts with introducing initial events in the system, otherwise nothing will happen. In our model we can start the simulation with one trigger event in the feedback channel of the town lp.

(2) Event information.
All events have a timestamp, the time at which they arrive in an lp and an outputchannel, the channel at which they leave the lp.
Besides this, each event may contain specific information, which depends on the event type. The customer event should have a boolean indicating whether he is by car or on foot. This information will be used in the exit demux to send the event respectively to the parking or the town lp. The pay-desk info event contains whether the pay-desk is open or closed (boolean).
The trigger and car event contain no specific information.

(3) The logical processes.
Next, we have to implement the logical processes. Its configuration are the parameters of a specific lp instance. For example, the entrance lp is a multiplexer with 2 input channels, thus the number of input channels of a mux is a configuration parameter. The state of an lp is all dynamic its information. For example, for a queue the state is the number of queued events. The behaviour of an lp determines how an incoming event is processed.
Let’s implement the supermarket lp’s:

Entrance (multiplexer)
Exit (demultiplexer)
Parking
Town
Floor
Queue (butcher, info)
Desk-select
Pay-desk

Simulation

The 8 first steps of the simulation.
Simulation thus mimicks the dynamics of the supermarket. This can then be used to measure properties of the system.
We can measure the total shopping time of a customer, by introducing the start time to the car/customer event. The town lp fills this property while creating the event and when the event leaves the supermarket, it can calculate the total time spent. Like this we introduce measurements to the simulation. Then we can calculate the average shopping time, the average time the customer has to queue, etcetera.
On the other hand we can study the dynamics of the waiting queue at the pay-desks. How does the queue evolve in time? What is the best decision strategy for closing and opening pay-desks? How many cashiers are necessary in total to keep the queueing time in certain limits? How many cashiers will be working at average? Etcetera.

Advanced remarks

Each customer shops around for a certain time, shopping time could thus be a property of the customer set by the town-lp, here it is calculated by the floor-lp. This is a ‘unnatural’ model decision which makes the model a bit simpler without changing the dynamics.
Additional to the initial events, all states have also to be initialised.
A specific car event is not really necessary, we can simply use a customer event together with the isOnFoot boolean.
The average-number-of-customers can be expressed in a function of time, e.g. there are more customers after the working hours. Then, we can study how we can handle these fluctuations over time.
The town lp can be decomposed into 2 sources (one for cars and one for customers on foot) and 2 sinks, it than becomes a what we call super-process: a logical group of lp's.