Discrete event simulation

Introduction

A few years ago Eliyahu Goldratt visited Alcatel Bell Telephone Manufacturing in Antwerp. Nowadays the company is part of Alcatel-Lucent Bell The purpose of the visit was to discuss the company’s profitability issues. In a meeting with the management of the company his first question was: “What is the goal of your manufacturing organization?” Several ideas and opinions were brought up by the members of the management. The only answer that everybody agreed upon was: “The goal of a firm is to make money and be profitable”. Without that goal a company’s existence is in danger. There are several financial tools for the Chief Financial Officer to measure this goal. The most important are net profit, return on investment and cash flow. But how can a Chief Operation Officer decide and act in order to improve these financial goals? Goldratt answers this question with his Theory of Constraints.

He defines a series of operational measures:

1. Throughput: Throughput is the rate at which a system generates money through sales or any other type of selling activities.
2. Inventory: Inventory is the monetary value of the goods that are still in the system and which a company intends to use in its processes in order to sell their products.
3. Operational Expense: Operational expense is the monetary value of the expenses of the system in order to turn inventory into throughput.

Goldratt explains to the management that they should use these measures to reach the Goal as follows: “Increase throughput while simultaneously reducing inventory and reducing operating expenses”

---PICUTURE---

Accoring to Goldratt’s theory, constraints are the only limits of the system that keeps the company from reaching the goal. There are 5 steps that have to be executed in order to reach the Goal.

1. Identify the system's constraints.
2. Decide how to exploit the system's constraints.
3. Subordinate everything else to that decision.
4. Elevate the system's constraints
5. If in one the previous steps a constraint has been broken, go back to step 1.

The system’s constraints can also be defined as the bottlenecks in a system. The only way to improve the overall system is by process improvements at the bottlenecks. Finding these bottlenecks can be done using discrete-event simulations. A simulation can show hidden excess inventories, inefficiencies and overproduction. In the fourth step, the management makes the decision how to improve the bottlenecks. The consequences of these process changes can immediately be visualized and studied by a simulation of these improvements. These simulations give the possibility to quickly evaluate several solutions at a low cost. As a result, the management can choose the best possible solution. The improvement of Goldratt’s Theory Of Constraints and lean manufacturing in general, is just one of the many useful applications of discrete-event simulations. More applications and examples of discrete event simulations will be explained later in this chapter after we provided a solid definition and introduced the general ideas of discrete event simulations.

Definition

Definition according to Richard E. Nance in "A History Of Discrete Event Simulations" (1993):

“Discrete event simulation utilizes a mathematical/logical model of a physical system that portrays state changes at precise points in simulated time. Both the nature of the state change and the time at which the change occurs mandate precise description. Customers waiting for service, the management of parts inventory or military combat are typical domains of discrete event simulation.”

A more theoretical top-down description of discrete-event simulations is the following: The start of a discrete- event simulation is a model. A model is the construction of a conceptual framework, used to represent a system. The specific characteristics of discrete-event simulation model are the following:

1. Stochastic: At least some of the models components are stochastic. This means that there is a certain factor of randomness in the model. This is represented by random number generators, which are explained in the terminology.
2. Dynamic: The time evolution of the system’s components is important. Time is a significant variable.
3. Discrete: The state of the system changes only significantly when events occur at discrete time instances.

---PICUTERE MODEL---

The difference with continuous simulations is the use of the factor time. The system evolves over time so the variables change continuously in a continuous simulation. Whereas in a discrete event simulation the events itself determine if something happens or not. Time can go by without anything happening.

A combination of discrete and dynamic simulation is called a combined simulation. The basic is a continuous simulation but certain discrete events interfere the continuity of the simulation making it a combined simulation.

Monte Carlo simulations are static simulations. This means that the factor time is not a significant variable in this model, whereas time evolution is important when dealing with discrete event simulations.

Terminology

Discrete-event simulations include the following important components:

Entities

Temporary entities are the elements that flow through the system. They wait in queues, follow a sequence of events and are specified by certain attributes. Most entities are introduced in a system according to a stochastic distribution. Examples of temporary entities are: parts of a good, customers and information messages.

Permanent entities remain in the system when the simulation is executed. They are used in the events to process the temporary entities. The processing time of the use of permanent entities is most of the time stochastically distributed. Examples of permanent entities are: operators, servers or machines.

Attributes

Entities own attributes that specify certain properties and states of the entity. They can affect how entities are handled during the sequence of the processes. They are not fixed through the flow so they can change by being processed. Examples of attributes are: priority and quality.

Events

Events change the state of the system. A sequence of events can be bundled as an activity. These events determine the timing and the flow of the simulation, hence the word discrete-event simulation. A typical example of events is the arrival of new entity, often used to start the simulation. The sequence of events ordered by time of occurrence forms an event list. Each simulation has at least one event list. This events list determines the mechanism for advancing the simulation time. This sequence of actions is also called event-scheduling. Every simulation also needs a stopping event or ending condition. This determines how long the simulation will run. Typical stopping events are a specific time in the future or a condition that the simulation itself fulfills.

Queue

Place where temporary entities wait an undetermined time before being accepted in an event. Some entities might have priority attributes to skip the queue. These queues can for example be used to locate overproduction or a bottleneck as mentioned in the introduction.

State variables

These variables describe the system at different points in time. They change according to the processes in the events.

Clock

The clock maintains the simulation time. The measurement units vary depending on the characteristics of the model. Because we are dealing with discrete-events, the time is not continuous but “jump” according to the events. The clock is also responsible for the timer of the events.

Random number generators

Most of the previous components need the possibility to generate random variables in order to simulate the stochastic distributions. Pseudorandom number generators are used to accomplish this.

Statistics

The result of a simulation should in the form of a report that gives important statistics about all the important components of the discrete-event simulation. These statistics are analyzed to make better decisions.

How to solve a discrete event simulation

There is a general algorithm to solve a standard discrete-event simulation model. The algorithm consists of several steps and the process is typically iterative. The algorithm should be used many times in order to obtain the most optimal solution.

1. Start with a real system and make sure you understand its characteristics. Determine the goals and objectives of the simulation. Why do we need the simulation? What problem do we have to solve? Answering these questions is essential to give meaning to the following steps.
2. Design a model of the real-life system. Which variables and aspects of the system are relevant for the simulation? Are there any variables or aspects that can be ignored to simplify the model?
3. Convert this model into a computational model that can be executed on a computer. When doing this an important aspect is the choice of the programming language. The two main possibilities are: a general-purpose programming language or a special-purpose simulation language. More information about these languages can be found in the Execution chapter.
4. The last step in this general algorithm is the analysis of the output of the computational model. By doing this you can fully understand the nature of the real system and also predict the output when variables of the model change.

On top of this algorithm we need to verify and validate the simulation model. We need to check if the computational model is consistent with the real system. This additional process is done iteratively over the steps in the general algorithm to ensure the quality of the simulation.

Execution

The execution of the computational model is one of the most important issues when dealing with simulations. Generally there are two beliefs about how to solve this issue.

Bratley, Fox, and Schrage (1987, page 219) state: “for any important large-scale real application we would write the programs in a standard general-purpose language, and avoid all the simulation languages we know."

On the other hand Law and Kelton (2000, page 204) state: “we believe, in general, that a modeler would be prudent to give serious consideration to the use of a simulation package."

General-purpose programming languages

Discrete-event simulation is a particular application of scientific computing. Therefore most general-purpose programming languages are suitable for solving discrete-event simulations. Nowadays C, C++ and Java are the most commonly used languages because of their popularity amongst all programmers. The main advantage of general-purpose programming languages is the flexibility and freedom they offer to programmers.

Special-purpose simulation languages or simulation languages

These simulation languages are specially build to solve simulation problems. They have built-in tools that offer many components of discrete-event simulations. The main advantage of simulation languages is the decrease in programming time. Another advantage is the use of animations. These animations make the models easier to understand. Some examples of simulation languages are: Simul8, ProModel and GPSS.