Discrete paradigms
Embedded Scribd iPaper - Requires Javascript and Flash Player
SIMULATION DISCRETE PARADIGMS
Pau Fonseca i Casas; pau@fib.upc.edu
Discrete simulation paradigms
Event Scheduling
Programació
d’esdeveniments (PE) Programación de eventos.
Process interaction
Interacció
de processos (IP) Interacción de procesos.
Activity scanning
Exploració
d’activitats (EA) Exploración de actividades.
ES: example
Time between arrivals a1 35 a2 a3 a4 12 29 47 Service time b1 b2 b3 b4 40 30 30 20
a5
12
b5
30
ES: chronogram
End of service (Exits)
A1 A2 A3
Server Server occupation
S2
S1
S3
Queue New clients
A2 A3 A4 A5
0
A1
35
12
29
47
12
Time
ES: Event list
event
event
event
event
event struct { Execution time: real Priority: enter Kind: enter } End struct
ES: event
Kind of event
Depends on the model definition. Exit event, enter event for a MM1 queue. Shows the time when the event enters in the simulation system. Shows when the simulation engine must run the event.
Creation time
Running time
Priority
ES: event
The time when the simulation engine runs the event. Priority must be taken in consideration only if two ore more) events have the same run time. The Kind of event allows to define the procedure that the simulation engine must run when the event is exe
ES
Simulation clock initialization.
Model initialization.
End of simulation?
Take the first event of the event list.
Run the event
Update the clock depending on the run time of the event.
Events list Statistical data preparation. Write the results.
ES: Arrive event procedure
Generation of the next arrival
Is the machine free?
Queue ++; Generation of the next end service. The state of the server is BUSY
ES: Exit event procedure
Statistics update. Remove the element of the system.
Is the queue empty?
Queue --;
Set the server state to FREE
Generation of the next end Service
ES: General event procedure
Modes state update and generation of the new events.
Stadistics update
New events must be generated?
New events generation
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
0
0
0
0
0
0
0
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
0
0
0
0,1509 1E+12
0
0
0
0
0
0
0
0
0
ES: Events evolution
Id 0 Time 0 0 1 0,1509 Next arrival 0 0,1509 0,5778 1E+12 0,93940 Next exit 0 Server state 0 0 1 Queue 0 0 0 Arrive 0 0 1 Exit 0 0 0
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
1 2
0
0 0,1509 0,5778
0
0,1509 0,5778 1,4772 1E+12
0
0,93940 0,93940
0
0 1 1
0
0 0 1
0
0 1 1
0
0 0 0
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
1 2 3
0
0 0,15099 0,57788 0,93940
0
0,1509 0,5778 1,4772 1,4772 1E+12
0
0,9394 0,9394 3,5225
0
0 1 1 1
0
0 0 1 0
0
0 1 1 0
0
0 0 0 1
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
1 2 3 4
0
0 0,1509 0,5778 0,9394 1,4772
0
0,1509 0,5778 1,4772 1,4772 1,5657 1E+12
0
0,9394 0,9394 3,5225 3,5225
0
0 1 1 1 1
0
0 0 1 0 1
0
0 1 1 0 1
0
0 0 0 1 0
Process interaction
Two different process typologies, P1 and P2:
P1 in the usual process of a G|G|1 system. The entity that arrives to the system needs the services of the server. The second process, P2, represents the process where the entities do no require the services of a server, however the entities suffers a delays.
PI: chronogram
Delay caused by the process interaction: For instance the use of the same resource. Process P2 P1 P1
Arrivals
PI: Event list
To simplify usually two list of activities are used. The activities that must be processed in the actual time, and the activities that must be processed in the future. The structure, however is quite similar to the structure shown in the Event Scheduling paradigm. Is important to remark the strong relation between the entity and the process linked to each entity.
PI:
Simulation model initialization
More activities in the CEC? no Move the activities from the FEC to the CEC si
Move the activities all that we can in its process
Clock update no
End of the simulation? si Statistics adquisition
Activity scanning
1.
2.
Analyze if the simulation engine can run some activity, this depends on the conditions of each activity, and run it until t. When the simulation engine cannot run more activities increment the clock with t.
AS: simulation engine
Model inicialization Can the engine run any activity No
Increment t
Yes
Run all the tasks of the selected task until t.
Simulation end?
Yes Statistics output.
No
Events evolution Examples
ES(Event scheduling) AS(Activity scanning)
Event scheduling events evolution
Using this data
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
0
0
0
0
0
0
0
Arrive: 1,6933 4,0012 5,2509 5,5315 5,6327 6,0014 7,3736
Exit: 1,8840 4,3038 5,6282 6,5012 7,0477
Event scheduling events evolution
Id Time Next arrival
1,6933
Next exit
1E+12
Server state
Queue
Arrive
Exit
Event scheduling events evolution
Id Time Next arrival
1,6933 1 1,6933 4,0012
Next exit
1E+12 1,8840
Server state
Queue
Arrive
Exit
1
0
1
0
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 1,6933 1,8840 4,0012 4,0012
Next exit
1E+12 1,8840 1E+12
Server state
Queue
Arrive
Exit
1 0
0 0
1 0
0 1
Event scheduling events evolution
Id Time Next arrival
1,693356 1 2 3 1,693356 1,884081 4,001288 4,001288 4,001288 5,250927
Next exit
1E+12 1,884081404 1E+12 4,303805741
Server state
Queue
Arrive
Exit
1 0 1
0 0 0
1 0 1
0 1 0
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 3 4 1,6933 1,8840 4,0012 4,3038 4,0012 4,0012 5,2509 5,2509
Next exit
1E+12 1,8840 1E+12 4,3038 1E+12
Server state
Queue
Arrive
Exit
1 0 1 0
0 0 0 0
1 0 1 0
0 1 0 1
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 3 4 5 1,6933 1,8840 4,0012 4,3038 5,2509 4,0012 4,0012 5,2509 5,2509 5,5315
Next exit
1E+12 1,8840 1E+12 4,3038 1E+12 5,6282
Server state
Queue
Arrive
Exit
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 1 0 1 0
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 3 4 1,6933 1,8840 4,0012 4,3038 4,0012 4,0012 5,2509 5,2509
Next exit
1E+12 1,8840 1E+12 4,3038 1E+12
Server state
Queue
Arrive
Exit
1 0 1 0
0 0 0 0
1 0 1 0
0 1 0 1
5
6 7 8 9 10 11
5,2509
5,5315 5,6282 5,6327 6,0014 6,5012 7,0477
5,5315
5,6327 5,6327 6,0014 7,3736 7,3736
5,6282
5,6282 6,5012 6,5012 6,5012 7,0477
1
1 1 1 1 1 1
0
1 0 1 2 1 0
1
1 0 1 1 0 0
0
0 1 0 0 1 1
Activity scanning events evolution
Using t=1. run the simulation until time = 6.
Id 1
Event Time Time
1
Next arrival
1,6933
Next exit
1E+12
Server Qu state eue
0 0
Arri ve
0
Exit
0
Next arrival
1,6933 4,0012 5,2509
Next exit
1,8840 4,3038 5,6282
5,5315
5,6327 6,0014
6,5012
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2
1
2 1,6933
1,6933
4,0012
1E+12
1,8840
0
1
0
0
0
1
0
0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3
1
2 2 1,6933 1,8840
1,6933
4,0012 4,0012
1E+12
1,8840 1E+12
0
1 0
0
0 0
0
1 0
0
0 1
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4
1
2 2 2 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012
1E+12
1,8840 1E+12 1E+12
0
1 0 0
0
0 0 0
0
1 0 0
0
0 1 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5
1
2 2 2 3 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012
1E+12
1,8840 1E+12 1E+12 1E+12
0
1 0 0 0
0
0 0 0 0
0
1 0 0 0
0
0 1 0 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6
1
2 2 2 3 4 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012 4,0012
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12
0
1 0 0 0 0
0
0 0 0 0 0
0
1 0 0 0 0
0
0 1 0 0 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6 7
1
2 2 2 3 4 5 4,0012 1,6933 1,8840
1,69335
4,0012 4,0012 4,0012 4,0012 4,0012 5,2509
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12 4,3038
0
1 0 0 0 0 1
0
0 0 0 0 0 0
0
1 0 0 0 0 1
0
0 1 0 0 0 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6 7 8
1
2 2 2 3 4 5 5 4,0012 4,3038 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012 4,0012 5,2509 5,2509
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12 4,3038 1E+12
0
1 0 0 0 0 1 0
0
0 0 0 0 0 0 0
0
1 0 0 0 0 1 0
0
0 1 0 0 0 0 1
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6 7 8 9
1
2 2 2 3 4 5 5 6 4,0012 4,3038 5,2509 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012 4,0012 5,2509 5,2509 5,5315
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12 4,3038 1E+12 5,6282
0
1 0 0 0 0 1 0 1
0
0 0 0 0 0 0 0 0
0
1 0 0 0 0 1 0 1
0
0 1 0 0 0 0 1 0
10
11 12
6
6 6
5,5315
5,6282 5,6327
5,6327
5,6327 6,0014
5,6282
6,5012 6,5012
1
1 1
1
0 1
1
0 1
0
1 0
SIMULATION DISCRETE PARADIGMS
Pau Fonseca i Casas; pau@fib.upc.edu
Discrete simulation paradigms
Event Scheduling
Programació
d’esdeveniments (PE) Programación de eventos.
Process interaction
Interacció
de processos (IP) Interacción de procesos.
Activity scanning
Exploració
d’activitats (EA) Exploración de actividades.
ES: example
Time between arrivals a1 35 a2 a3 a4 12 29 47 Service time b1 b2 b3 b4 40 30 30 20
a5
12
b5
30
ES: chronogram
End of service (Exits)
A1 A2 A3
Server Server occupation
S2
S1
S3
Queue New clients
A2 A3 A4 A5
0
A1
35
12
29
47
12
Time
ES: Event list
event
event
event
event
event struct { Execution time: real Priority: enter Kind: enter } End struct
ES: event
Kind of event
Depends on the model definition. Exit event, enter event for a MM1 queue. Shows the time when the event enters in the simulation system. Shows when the simulation engine must run the event.
Creation time
Running time
Priority
ES: event
The time when the simulation engine runs the event. Priority must be taken in consideration only if two ore more) events have the same run time. The Kind of event allows to define the procedure that the simulation engine must run when the event is exe
ES
Simulation clock initialization.
Model initialization.
End of simulation?
Take the first event of the event list.
Run the event
Update the clock depending on the run time of the event.
Events list Statistical data preparation. Write the results.
ES: Arrive event procedure
Generation of the next arrival
Is the machine free?
Queue ++; Generation of the next end service. The state of the server is BUSY
ES: Exit event procedure
Statistics update. Remove the element of the system.
Is the queue empty?
Queue --;
Set the server state to FREE
Generation of the next end Service
ES: General event procedure
Modes state update and generation of the new events.
Stadistics update
New events must be generated?
New events generation
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
0
0
0
0
0
0
0
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
0
0
0
0,1509 1E+12
0
0
0
0
0
0
0
0
0
ES: Events evolution
Id 0 Time 0 0 1 0,1509 Next arrival 0 0,1509 0,5778 1E+12 0,93940 Next exit 0 Server state 0 0 1 Queue 0 0 0 Arrive 0 0 1 Exit 0 0 0
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
1 2
0
0 0,1509 0,5778
0
0,1509 0,5778 1,4772 1E+12
0
0,93940 0,93940
0
0 1 1
0
0 0 1
0
0 1 1
0
0 0 0
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
1 2 3
0
0 0,15099 0,57788 0,93940
0
0,1509 0,5778 1,4772 1,4772 1E+12
0
0,9394 0,9394 3,5225
0
0 1 1 1
0
0 0 1 0
0
0 1 1 0
0
0 0 0 1
ES: Events evolution
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
1 2 3 4
0
0 0,1509 0,5778 0,9394 1,4772
0
0,1509 0,5778 1,4772 1,4772 1,5657 1E+12
0
0,9394 0,9394 3,5225 3,5225
0
0 1 1 1 1
0
0 0 1 0 1
0
0 1 1 0 1
0
0 0 0 1 0
Process interaction
Two different process typologies, P1 and P2:
P1 in the usual process of a G|G|1 system. The entity that arrives to the system needs the services of the server. The second process, P2, represents the process where the entities do no require the services of a server, however the entities suffers a delays.
PI: chronogram
Delay caused by the process interaction: For instance the use of the same resource. Process P2 P1 P1
Arrivals
PI: Event list
To simplify usually two list of activities are used. The activities that must be processed in the actual time, and the activities that must be processed in the future. The structure, however is quite similar to the structure shown in the Event Scheduling paradigm. Is important to remark the strong relation between the entity and the process linked to each entity.
PI:
Simulation model initialization
More activities in the CEC? no Move the activities from the FEC to the CEC si
Move the activities all that we can in its process
Clock update no
End of the simulation? si Statistics adquisition
Activity scanning
1.
2.
Analyze if the simulation engine can run some activity, this depends on the conditions of each activity, and run it until t. When the simulation engine cannot run more activities increment the clock with t.
AS: simulation engine
Model inicialization Can the engine run any activity No
Increment t
Yes
Run all the tasks of the selected task until t.
Simulation end?
Yes Statistics output.
No
Events evolution Examples
ES(Event scheduling) AS(Activity scanning)
Event scheduling events evolution
Using this data
Id Time Next arrival Next exit Server state Queue Arrive Exit
0
0
0
0
0
0
0
0
Arrive: 1,6933 4,0012 5,2509 5,5315 5,6327 6,0014 7,3736
Exit: 1,8840 4,3038 5,6282 6,5012 7,0477
Event scheduling events evolution
Id Time Next arrival
1,6933
Next exit
1E+12
Server state
Queue
Arrive
Exit
Event scheduling events evolution
Id Time Next arrival
1,6933 1 1,6933 4,0012
Next exit
1E+12 1,8840
Server state
Queue
Arrive
Exit
1
0
1
0
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 1,6933 1,8840 4,0012 4,0012
Next exit
1E+12 1,8840 1E+12
Server state
Queue
Arrive
Exit
1 0
0 0
1 0
0 1
Event scheduling events evolution
Id Time Next arrival
1,693356 1 2 3 1,693356 1,884081 4,001288 4,001288 4,001288 5,250927
Next exit
1E+12 1,884081404 1E+12 4,303805741
Server state
Queue
Arrive
Exit
1 0 1
0 0 0
1 0 1
0 1 0
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 3 4 1,6933 1,8840 4,0012 4,3038 4,0012 4,0012 5,2509 5,2509
Next exit
1E+12 1,8840 1E+12 4,3038 1E+12
Server state
Queue
Arrive
Exit
1 0 1 0
0 0 0 0
1 0 1 0
0 1 0 1
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 3 4 5 1,6933 1,8840 4,0012 4,3038 5,2509 4,0012 4,0012 5,2509 5,2509 5,5315
Next exit
1E+12 1,8840 1E+12 4,3038 1E+12 5,6282
Server state
Queue
Arrive
Exit
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 1 0 1 0
Event scheduling events evolution
Id Time Next arrival
1,6933 1 2 3 4 1,6933 1,8840 4,0012 4,3038 4,0012 4,0012 5,2509 5,2509
Next exit
1E+12 1,8840 1E+12 4,3038 1E+12
Server state
Queue
Arrive
Exit
1 0 1 0
0 0 0 0
1 0 1 0
0 1 0 1
5
6 7 8 9 10 11
5,2509
5,5315 5,6282 5,6327 6,0014 6,5012 7,0477
5,5315
5,6327 5,6327 6,0014 7,3736 7,3736
5,6282
5,6282 6,5012 6,5012 6,5012 7,0477
1
1 1 1 1 1 1
0
1 0 1 2 1 0
1
1 0 1 1 0 0
0
0 1 0 0 1 1
Activity scanning events evolution
Using t=1. run the simulation until time = 6.
Id 1
Event Time Time
1
Next arrival
1,6933
Next exit
1E+12
Server Qu state eue
0 0
Arri ve
0
Exit
0
Next arrival
1,6933 4,0012 5,2509
Next exit
1,8840 4,3038 5,6282
5,5315
5,6327 6,0014
6,5012
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2
1
2 1,6933
1,6933
4,0012
1E+12
1,8840
0
1
0
0
0
1
0
0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3
1
2 2 1,6933 1,8840
1,6933
4,0012 4,0012
1E+12
1,8840 1E+12
0
1 0
0
0 0
0
1 0
0
0 1
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4
1
2 2 2 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012
1E+12
1,8840 1E+12 1E+12
0
1 0 0
0
0 0 0
0
1 0 0
0
0 1 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5
1
2 2 2 3 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012
1E+12
1,8840 1E+12 1E+12 1E+12
0
1 0 0 0
0
0 0 0 0
0
1 0 0 0
0
0 1 0 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6
1
2 2 2 3 4 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012 4,0012
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12
0
1 0 0 0 0
0
0 0 0 0 0
0
1 0 0 0 0
0
0 1 0 0 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6 7
1
2 2 2 3 4 5 4,0012 1,6933 1,8840
1,69335
4,0012 4,0012 4,0012 4,0012 4,0012 5,2509
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12 4,3038
0
1 0 0 0 0 1
0
0 0 0 0 0 0
0
1 0 0 0 0 1
0
0 1 0 0 0 0
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6 7 8
1
2 2 2 3 4 5 5 4,0012 4,3038 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012 4,0012 5,2509 5,2509
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12 4,3038 1E+12
0
1 0 0 0 0 1 0
0
0 0 0 0 0 0 0
0
1 0 0 0 0 1 0
0
0 1 0 0 0 0 1
Activity scanning events evolution
Id
Time
Event Time
Next arrival
Next exit
Server state
Queue
Arrive
Exit
1
2 3 4 5 6 7 8 9
1
2 2 2 3 4 5 5 6 4,0012 4,3038 5,2509 1,6933 1,8840
1,6933
4,0012 4,0012 4,0012 4,0012 4,0012 5,2509 5,2509 5,5315
1E+12
1,8840 1E+12 1E+12 1E+12 1E+12 4,3038 1E+12 5,6282
0
1 0 0 0 0 1 0 1
0
0 0 0 0 0 0 0 0
0
1 0 0 0 0 1 0 1
0
0 1 0 0 0 0 1 0
10
11 12
6
6 6
5,5315
5,6282 5,6327
5,6327
5,6327 6,0014
5,6282
6,5012 6,5012
1
1 1
1
0 1
1
0 1
0
1 0
