Week 1
Discrete event simulation (DES)
Framework for modelling systems by DES. A system is modelled in terms of its state at each
point in time. This is appropriate for systems where changes occur only at discrete points in
time. These points in time are when events occur and these events are of main importance
State variables
The system state variables contain the information on the system content
Event
Instantaneous occurrence that may change the state of the system (a state transition). Each
event has a time-stamp indicating when it occurs. This includes the end simulation event
Simulation clock
The simulation clock is the variable in a simulation model that gives the current value of
simulated time. Used to keep track of the current value of simulated time as the simulation
proceeds, and to advance simulated time from one value to another
Next-event time advance
Initialize simulation clock to 0. Determine times of occurrence of future events (event list).
Clock advances to next (most imminent) event, which is executed. Continue until stopping
rule is satisfied. Clock jumps from one event time to the next
Components DES model
The components of a DES model are:
- System state – variables to describe state
- Simulation clock – current value of simulated time
- Event list – times of future events
- Statistical counters – variables for storing information about system performance
- Initialization routine – initialize model at time 0
- Timing routine – choose next event time and type, then advance the clock
- Event routines – carry out logic for each event type
- Library routines – utilities to generate random variables, etc.
- Report generator – to summarize and report results at the and
- Main program – ties routines together and executes in right order
Variables for queueing systems
- 𝐷! : delay in queue of 𝑖 "# customer
- 𝑊! = 𝐷! + 𝑆! : residence time in system of 𝑖 "# customer (delay + service time)
- 𝑄(𝑡): number of customers in queue at time 𝑡
- 𝐿(𝑡): number of customers in system at time 𝑡
- 𝑇! : total time during the simulation that the queue is of length 𝑖
- 𝑇(𝑛): time required to observe 𝑛 delays in the queue
$!
- 𝑝! = $(&) : expected proportion of the time that 𝑄(𝑡) equals to 𝑖
- 𝐵(𝑡) = 1 if the server is busy at time 𝑡, and 𝐵(𝑡) = 0 is the server is idle at time 𝑡
Performance measures for queueing systems
∑" + ∑" +
- 𝑑 = lim !#$ ! : steady-state average delay, estimated by 𝑑6 (𝑛) = !#$ !
& &
&→)
∑"
!#$ ,! ∑"
!#$ ,!
- 𝑊 = lim &
: steady-state average residence time, estimated by 𝑤
8(𝑛) = &
&→)
%
∫& .(")/"
- 𝑄(𝑛) = lim $
: steady-state time-average number in queue, estimated by
$→)
%(")
∑"
!#& !$! ∫& .(")/"
𝑞:(𝑛) = $(&)
= $
%
∫& 0(")/"
- 𝐿(𝑛) = lim $
: steady-state time-average number in system
$→)
, %(")
∫& 1(")/"
- 𝑢:(𝑛) = $(&)
: expected utilization of the server
Event routine
1. Update system state
2. Update statistical counters
3. Generate future events and add to event list
Single server queuing system
- State variables: [𝑧, 𝑄], 𝑧 is binary variable, representing idle or busy, 𝑄 is a vector
representing the waiting customers
- Events: arrival and departure
- Event list: vector [𝑡2 , 𝑡+ ] of scheduled next occurrences of two events
- Statistical counters: 𝑛 (number of customers served), total delay, area under 𝑄(𝑡), area
under 𝐵(𝑡)
Queuing system with two servers in series
- State variables: [𝑧3 , 𝑧4 ; 𝑄3 , 𝑄4 ]
- Event list: [𝑡2 , 𝑡3 , 𝑡4 ], 𝑡2 is the arrival time of a new customer, 𝑡! is the departure time of
a serving customer from server 𝑖
- Statistical counters: 𝑛 (number of customers served, waiting time at server 𝑖 (a vector)
Single queue with two parallel servers
The state variables are [𝑧3 , 𝑧4 , 𝑄 ] and the event list is [𝑡2 , 𝑡3 , 𝑡4 ]
(𝑠, 𝑆) policy with lost sales
(𝑠, 𝑆) says when to order: if the stock drops below 𝑠, and how many to order: up to 𝑆. If
there is no inventory and there is a customer, the sale is lost
Inventory problem
Customers arrive at a Poisson rate of 𝜆, with random demand. The time between ordering
and receiving new supply is 𝐿. The sale price is 𝑟 per item, the holding costs are ℎ per item
per unit time, the ordering costs are 𝑐(𝑦) for ordering 𝑦 items. We want to estimate the
profit for different values of 𝑠 and 𝑆, and choose the best combination.
- State variables: (𝑥, 𝑦), 𝑥 is the amount of inventory on hand, 𝑦 is the amount on order
- Events: a customer arrival (demand), and an order arrival (supply)
- Event list: [𝑡5 , 𝑡3 ], 𝑡5 is the arrival time of the next customer, 𝑡3 is the time at which the
order will be delivered
- Statistical counters: 𝐶, the total amount of ordering cost by time 𝑡; 𝐻, the total amount
of inventory holding costs by time 𝑡; 𝑅: the total amount of revenue by time 𝑡
67879
The average profit per time unit is $
Repair problem
The system crashes when no spares are available for a failed machine. If a machine fails, it
goes to the queue for repair. If it is repaired, it becomes available as a spare. Repair times
and time between two failures are random variables. There are 𝑛 + 𝑠 machines available, 𝑛
are put to use and 𝑠 are kept as spares.
- System state variables: 𝑟, the number of machines that are down at time 𝑡
- Events: machine breads down and machine repair is completed
- Event lists: 𝑡3 ≤ 𝑡4 ≤ ⋯ ≤ 𝑡& , 𝑡 ∗ , 𝑡! ’s are the times (in order) at which 𝑛 machines
presently in use will fail, 𝑡 ∗ is the time at which the machine currently under repair will
become available
- Statistical counters: 𝑇, the time at which the system crashes
Discrete event simulation (DES)
Framework for modelling systems by DES. A system is modelled in terms of its state at each
point in time. This is appropriate for systems where changes occur only at discrete points in
time. These points in time are when events occur and these events are of main importance
State variables
The system state variables contain the information on the system content
Event
Instantaneous occurrence that may change the state of the system (a state transition). Each
event has a time-stamp indicating when it occurs. This includes the end simulation event
Simulation clock
The simulation clock is the variable in a simulation model that gives the current value of
simulated time. Used to keep track of the current value of simulated time as the simulation
proceeds, and to advance simulated time from one value to another
Next-event time advance
Initialize simulation clock to 0. Determine times of occurrence of future events (event list).
Clock advances to next (most imminent) event, which is executed. Continue until stopping
rule is satisfied. Clock jumps from one event time to the next
Components DES model
The components of a DES model are:
- System state – variables to describe state
- Simulation clock – current value of simulated time
- Event list – times of future events
- Statistical counters – variables for storing information about system performance
- Initialization routine – initialize model at time 0
- Timing routine – choose next event time and type, then advance the clock
- Event routines – carry out logic for each event type
- Library routines – utilities to generate random variables, etc.
- Report generator – to summarize and report results at the and
- Main program – ties routines together and executes in right order
Variables for queueing systems
- 𝐷! : delay in queue of 𝑖 "# customer
- 𝑊! = 𝐷! + 𝑆! : residence time in system of 𝑖 "# customer (delay + service time)
- 𝑄(𝑡): number of customers in queue at time 𝑡
- 𝐿(𝑡): number of customers in system at time 𝑡
- 𝑇! : total time during the simulation that the queue is of length 𝑖
- 𝑇(𝑛): time required to observe 𝑛 delays in the queue
$!
- 𝑝! = $(&) : expected proportion of the time that 𝑄(𝑡) equals to 𝑖
- 𝐵(𝑡) = 1 if the server is busy at time 𝑡, and 𝐵(𝑡) = 0 is the server is idle at time 𝑡
Performance measures for queueing systems
∑" + ∑" +
- 𝑑 = lim !#$ ! : steady-state average delay, estimated by 𝑑6 (𝑛) = !#$ !
& &
&→)
∑"
!#$ ,! ∑"
!#$ ,!
- 𝑊 = lim &
: steady-state average residence time, estimated by 𝑤
8(𝑛) = &
&→)
%
∫& .(")/"
- 𝑄(𝑛) = lim $
: steady-state time-average number in queue, estimated by
$→)
%(")
∑"
!#& !$! ∫& .(")/"
𝑞:(𝑛) = $(&)
= $
%
∫& 0(")/"
- 𝐿(𝑛) = lim $
: steady-state time-average number in system
$→)
, %(")
∫& 1(")/"
- 𝑢:(𝑛) = $(&)
: expected utilization of the server
Event routine
1. Update system state
2. Update statistical counters
3. Generate future events and add to event list
Single server queuing system
- State variables: [𝑧, 𝑄], 𝑧 is binary variable, representing idle or busy, 𝑄 is a vector
representing the waiting customers
- Events: arrival and departure
- Event list: vector [𝑡2 , 𝑡+ ] of scheduled next occurrences of two events
- Statistical counters: 𝑛 (number of customers served), total delay, area under 𝑄(𝑡), area
under 𝐵(𝑡)
Queuing system with two servers in series
- State variables: [𝑧3 , 𝑧4 ; 𝑄3 , 𝑄4 ]
- Event list: [𝑡2 , 𝑡3 , 𝑡4 ], 𝑡2 is the arrival time of a new customer, 𝑡! is the departure time of
a serving customer from server 𝑖
- Statistical counters: 𝑛 (number of customers served, waiting time at server 𝑖 (a vector)
Single queue with two parallel servers
The state variables are [𝑧3 , 𝑧4 , 𝑄 ] and the event list is [𝑡2 , 𝑡3 , 𝑡4 ]
(𝑠, 𝑆) policy with lost sales
(𝑠, 𝑆) says when to order: if the stock drops below 𝑠, and how many to order: up to 𝑆. If
there is no inventory and there is a customer, the sale is lost
Inventory problem
Customers arrive at a Poisson rate of 𝜆, with random demand. The time between ordering
and receiving new supply is 𝐿. The sale price is 𝑟 per item, the holding costs are ℎ per item
per unit time, the ordering costs are 𝑐(𝑦) for ordering 𝑦 items. We want to estimate the
profit for different values of 𝑠 and 𝑆, and choose the best combination.
- State variables: (𝑥, 𝑦), 𝑥 is the amount of inventory on hand, 𝑦 is the amount on order
- Events: a customer arrival (demand), and an order arrival (supply)
- Event list: [𝑡5 , 𝑡3 ], 𝑡5 is the arrival time of the next customer, 𝑡3 is the time at which the
order will be delivered
- Statistical counters: 𝐶, the total amount of ordering cost by time 𝑡; 𝐻, the total amount
of inventory holding costs by time 𝑡; 𝑅: the total amount of revenue by time 𝑡
67879
The average profit per time unit is $
Repair problem
The system crashes when no spares are available for a failed machine. If a machine fails, it
goes to the queue for repair. If it is repaired, it becomes available as a spare. Repair times
and time between two failures are random variables. There are 𝑛 + 𝑠 machines available, 𝑛
are put to use and 𝑠 are kept as spares.
- System state variables: 𝑟, the number of machines that are down at time 𝑡
- Events: machine breads down and machine repair is completed
- Event lists: 𝑡3 ≤ 𝑡4 ≤ ⋯ ≤ 𝑡& , 𝑡 ∗ , 𝑡! ’s are the times (in order) at which 𝑛 machines
presently in use will fail, 𝑡 ∗ is the time at which the machine currently under repair will
become available
- Statistical counters: 𝑇, the time at which the system crashes
