Scribd
Upload
56 views26 pages

Event Scheduling Algorithm in IE 303

This document discusses event scheduling algorithms used in discrete-event simulation. It explains that events (like arrivals or service completions) and activities (like service times) are recorded in a future event list with their associated times. At each event, the next event is removed from the list and the simulation clock is advanced. New future events like additional arrivals or completions are added to the list. It provides an example of simulating a single server queue using this approach and tracking outputs like number of services, utilization, waiting times and queue lengths. List processing methods for the future event list like adding and removing records are also covered.

Uploaded by

Bhagya Patil
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
56 views26 pages

Event Scheduling Algorithm in IE 303

This document discusses event scheduling algorithms used in discrete-event simulation. It explains that events (like arrivals or service completions) and activities (like service times) are recorded in a future event list with their associated times. At each event, the next event is removed from the list and the simulation clock is advanced. New future events like additional arrivals or completions are added to the list. It provides an example of simulating a single server queue using this approach and tracking outputs like number of services, utilization, waiting times and queue lengths. List processing methods for the future event list like adding and removing records are also covered.

Uploaded by

Bhagya Patil
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

IE 303

Discrete-Event Simulation

LECTURE 3: EVENT-SCHEDULING
ALGORITHM
Outline

 Event Scheduling Algorithm


 Single Server Queue (Revisited)
 List processing
Review of the Previous Lecture

 Properties of random random numbers


 Uniformity

 Independence from history

 As sample size->∞, histogram of random numbers ->


uniform distr.
 Coin tossing game
 Single server queue

-> -> -> ->


Event Scheduling Algorithm

 In our simulations so far, we went trough entities,


e.g. arriving customers, daily demand to
newsvendor, coin tosses,

 What if our simulation is more complex?


 Example: Assume we are simulating a port. We have 3 types of
ships:
 Container ships, Bulk carriers, Tankers
 Each ship should be served by different types of machinery…
Event Scheduling Algorithm

 Keeping track of events in a simulation model is


much harder if we do it through ship arrivals…

 So, we use event scheduling algorithm:


 The idea of the algorithm is at each event occurrence (activity)
e.g. arrival of a customer, start of production etc,

future event is generated and written into Future Event List


(FEL).
Event Scheduling Algorithm

 Activity vs. Delay:


Activity a duration of time of specified length (statistical distributions)
(e.g. service time or interarrival time), which is known when it begins.
Delay a duration of time of unspecified indefinite length, which is not
known until it ends (e.g. a customer’s delay in a last-in-first-out
waiting line)

Single Server Queue:


Event: Arrivals of customers, service completion in the server
Activity: Service time
Delay: customers’ waiting in the queue
Event Scheduling Algorithm

At any given time t, the FEL contains all previously


scheduled events and their associated event times in
chronological order:

t < t1 ≤ t2 ≤ t3 ≤ ··· ≤ tn

Time t is the value of CLOCK, current value of


simulated time. The event associated t1 is the next
event (imminent event) that will occur.
Event Scheduling Algorithm

 As time proceeds, the system state and future events


and statistics are handled with such a table.
Event Scheduling Algorithm

 Also, every simulation should have a stopping event


(E), which should be kept in FEL.
 How would you draw the flow diagram of this
algorithm?
Event Scheduling Algorithm
Event Scheduling Algorithm

 Lets build a simulation of a single server queue using


the event scheduling algorithm…
Event Scheduling Algorithm

 Four output measures:

NS : Number of service starts . It will be incremented every time the


service of a new customer is started.
B : Server utilization is defined by total server busy time
divided by total time, TE .
TE : Average waiting time is defined by total waiting time number
of service (W/ NS).
W : Average queue length
LS : Service length
LQ : Queue length
Event Scheduling Algorithm
Event Scheduling Algorithm
Dump Truck Example
Dump Truck Example
Dump Truck Example
Dump Truck Example
Dump Truck Example
Dump Truck Example
Dump Truck Example
Dump Truck Example
Dump Truck Example
List Processing

 As can be seen FEL plays a crucial role in the


simulation algorithm.

 It is important to know and manage FEL list which


can get very long in real-life simulation applications.

 FEL can be stored in arrays by a computer.


List Processing

 Storing event list in arrays is a straightforward way.

 It has pros and cons at the same time. From any


perspective it is important to establish main
operations on FEL list:

 Removing a record from the top of the list


 Removing a record from any location on the list
 Adding a record to the bottom or top of the list
 Adding a record to an arbitrary location.
END OF LECTURE 4

Next Lecture Chapter 5.1, 5.3, 5.4

You might also like