Transcript Introduction (Packages) (44 slides)

Management of the Simulated
Clock
Fixed-time Increment
Variable-time Increment
Introduction(Packages)
1
Flowchart for arrival routine,
queueing model
Arrival
event
Schedule the next
arrival event
Yes
Write error
message and stop
simulation
Yes
Is
the server
busy?
No
Add 1to the
number in queue
Set delay = 0
for this customer
and gather statistics
Is
the queue
Full?
Add 1 to the
number of
customers delayed
No
Store time of
arrival of this
customer
Make the
server busy
Schedule a
departure event
for this customer
Return
Flowchart for departure routine,
queueing model
Yes
Departure
event
Is
the queue
empty?
No
Make the
server idle
Subtract 1 from
the number in
queue
Eliminate departure
event from
consideration
Compute delay of
customer entering service
and gather statistics
Add 1 to the number
of customers delayed
Schedule a
departure event
for this customer
Move each customer
in queue (if any)
up one place
Return
Distribution of time between arrivals
Time between
Arrivals(min.)
1
2
3
4
5
6
7
8
Cumulative Random digit
Probability Probability
Assignment
0.125
0.125
0.125
0.125
0.125
0.125
0.125
0.125
0.125
0.250
0.375
0.500
0.625
0.750
0.875
1.000
Introduction(Packages)
000-125
126-250
251-375
376-500
501-625
626-750
751-875
876-000
4
Service Time Distribution
Service Time
(Minutes) Probability
1
2
3
4
5
6
0.10
0.20
0.30
0.25
0.10
0.05
Cumulative
Probability
Random digit
Assignment
0.10
0.30
0.60
0.85
0.95
1.00
01 - 10
11 - 30
31 - 60
61- 85
86 - 95
96 - 00
Introduction(Packages)
5
Time-between-arrival Determination
Random Time btwn
Digit
Arrivals
Customer
(Minutes)
1
2
3
4
5
6
7
8
9
10
_
913
727
015
948
309
922
753
235
302
_
8
6
1
8
3
8
7
2
3
Random Time btwn
Digit
Arrivals
Customer
(Minutes)
11
12
13
14
15
16
17
18
19
20
Introduction(Packages)
109
093
607
738
359
888
106
212
493
535
1
1
5
6
3
8
1
2
4
5
6
Service Times Generated
Random
Customer
Digit
1
2
3
4
5
6
7
8
9
10
84
10
74
53
17
79
91
67
89
38
Service
Time
(Minutes)
4
1
4
3
2
4
5
4
5
3
Random
Customer
Digit
11
12
13
14
15
16
17
18
19
20
Introduction(Packages)
32
94
79
05
79
84
52
55
30
50
Service
Time
(Minutes)
3
5
4
1
5
4
3
3
2
3
7
Work Sheet
Customer
Number
Clock
Time
Arrival
1
0
.
.
.
.
.
.
.
.
.
Event Type
Findings from the Simulation
1. Average waiting time for a customer
Total time customers wait in queue(minute)
Total number of customers
56

 2.8(min)
20
Introduction(Packages)
9
Findings from the Simulation(cont)
2. Prob. that a customer has to wait in a queue
Number of customers who wait
Total number of customers
13

 0.65
20
Introduction(Packages)
10
Findings from the Simulation(cont)
3. Proportion of idle time of the server
Total idle time of server(minute)
Total run time of simulation(minute)
18

 0.21
86
Thus, the probability of the server
being busy is the complement of 0.21,
or 0.79
Introduction(Packages)
11
The Able-Baker carhop problem
The purpose of this example is to indicate the
simulation procedure when there is more
than one channel.
Consider a drive-in restaurant where carhops
take orders and bring food to the car.
Cars arrive in the manner shown in the
following table.
Introduction(Packages)
12
The Able-Baker carhop problem
(Interarrival distribution of cars)
Time between
Arrivals
Cumulative
(Minutes)
Probability Probability
1
2
3
4
0.25
0.40
0.20
0.15
0.25
0.65
0.85
1.00
Introduction(Packages)
Random
Digit
Assignment
01-25
26-65
66-85
86-00
13
The Able-Baker carhop problem
(continued)
There are two car hops -- Able and Baker.
Able is better able to do the job, and works
somewhat faster than Baker.
The distribution of service times of Able and
Baker is following.
Introduction(Packages)
14
The Able-Baker carhop problem
(Service Distribution of Able)
Service
Time
(Minutes)
2
3
4
5
Random
Cumulative
Digit
Probability Probability Assignment
0.30
0.28
0.25
0.17
0.30
0.58
0.83
1.00
Introduction(Packages)
01-30
31-58
59-83
84-00
15
The Able-Baker carhop problem
(Service Distribution of Baker)
Service
Time
(Minutes)
3
4
5
6
Random
Cumulative
Digit
Probability Probability Assignment
0.35
0.25
0.20
0.20
0.35
0.60
0.80
1.00
Introduction(Packages)
01-35
36-60
61-80
81-00
16
The Able-Baker carhop problem
(Continued)
l Over the 62-minute period Able is busy 90% of
the time.
2 Baker was busy only 69% of the time. The
seniority rule keeps Baker less busy.
3 Nine of 26 or about 35% of the arrivals had to
wait. The average waiting time for all
customers was only about 0.42 minute, or 25
seconds, which is very small.
Introduction(Packages)
17
The Able-Baker carhop problem
(Continued)
4 Those 9 who did have to wait only waited an
average of 1.22 minutes, which is quite low.
5 In summary, this system seems well balanced.
One server cannot handle all the dinners, and
three servers would probably be too many.
Adding an additional server would surely
reduce the waiting time to nearly zero.
However, the cost of waiting would have to be
quite high to justify an additional worker.
Introduction(Packages)
18
GPSS (Process-Oriented)
Diagram
Logical Level
GPSS Implementation
Level
PERM ANENT
-Created
Implicitly
GPSS Equipm e nt Entitie s
-Facilities, Storages,
Queues, sw itches,...
ELEM ENTS
-Entities and
Attributes
Model
Structure
OPERATIONS
TEM PORARY
- created/
Destroyed
Dynamically
BLOCKS
- Activated
by Entering
Transactions
Introduction(Packages)
TRANSACTIONS
-Attributes
Flowing
Through
Connected
to form
NETWORK
19
GPSS Events
Current-Event Chain:
Transaction with BDT <= C1
Future-Event Chain:
Transaction with BDT > C1
Introduction(Packages)
20
GPSS Events(continued)
Note
Events must be executed chronologically, so
chains are maintained in ascending order
Current-Event Chain performs an additional
tasks(i.e. maintains by priority)
Introduction(Packages)
21
GPSS Execution Trace
The system. Four transactions enter the system at
intervals of 3 time units, starting at time unit 1.
They try to seize facility MACH for 4 time units
and then try to enter storage BUFFE (with
capacity 2) before releasing MACH.
After 9 time units in BUFFE, they leave storage
and terminate. In this model the number of
transactions must be limited because it has been
devised to cause catastrophic congestion.
Introduction(Packages)
22
GPSS Sample instructions
BUFFE
STORAGE
GENERATE
QUEUE
SEIZE
DEPART
ADVANCE
ENTER
RELEASE
ADVANCE
LEAVE
TERMINATE
START
Introduction(Packages)
2
3,,1,4
WAIT
MACH
WAIT
4
BUFFE
MACH
9
BUFFE
1
4
23
GPSS (Process-Oriented)
Diagram
no1
0
1
no1
no2 no3
no4
4
7
10
15
no2
no3
no4
20
25
30
Queue WAIT
no1
no2
no3
no4
1
5
9
14
Facility
MACH
18
no4
no2
no1
5
27
9
14
no1
18
no2
Introduction(Packages)
no3
Storage
BUFFE
23
no3
no4
24
GPSS/H Block Diagram,
Queueing Model
GENERATE
RVEXPO(1,1.0)
QUEUE
SERVERQ
SEIZE
SERVER
LVEQ
N$LVEQ
Create
Arriving
Custome
r
DEPART
SERVERQ
(STOP)
TEST
ADVANCE
RVEXPO(2,0.5)
Enter the
Queue
Seize
the
Server
1000
L
Delay for
Service
SER
VER
(STOP)
Leave
the
Queue
Introduction(Packages)
RELEASE
TERMINATE
Test for the
termination
of the run
1
Release
the
Server
Customers
Depart
25
GPSS/H - Queueing Model
1 * SIMULATION OF THE M/M/1 QUEUE
2*
3
SIMULATE
4
GENERATE RVEXPO(1,1,0)
Create Arriving Customer
5
QUEUE
SERVERQ
Enter the Queue
6
SEIZE
SERVER
Seize the Server
7 LVEQ DEPART
SERVERQ
Leave the Queue
8
TEST L
N$LVEQ,1000,STOP Test for Termination
9
ADVANCE
RVEXPO(2,0.5)
Delay for service
10 STOP RELEASE
SERVER
Customers Depart
11
TERMINATE 1
12 *
13 * CONTROL STATEMENT
14 *
15
START
1000
Make 1 simulation run
16
END
Introduction(Packages)
26
GPSS/H standard output report,
Queueing Model
RELATIVE CLOCK: 1014.1565
BLOCK CURRENT
1
2
3
LVEQ
5
6
STOP
8
ABSOLUTE CLOCK:1014.1565
TOTAL
1000
1000
1000
1000
1000
999
1000
1000
-- AVG-UTIL-DURING-FACILITY TOTAL AVAIL UNAVL ENTRIES AVG
CURRENT
TIME TIME TIME
TIME/XACT STATUS
SERVER
0.516
1000 0.523
AVAIL
Introduction(Packages)
27
GPSS/H standard output report,
Queueing Model(Continued)
QUEUE MAXIMUM AVERAGE TOTAL ZERO PERCENT
CONTENTS CONTENTS ENTRIES ENTRIES ZEROS
SERVERQ
8
0.605
1000
454
45.4
QUEUE AVERAGE $AVERAGE
TIME/UNIT TIME/UNIT
SERVERQ
0.614
1.124
QTABLE
CURRENT
NUMBER CONTENTS
0
RANDOM ANTITHETIC INITIAL CURRENT SAMPLE CHI-SQUARE
STREAM VARIATES
POS.
POS. COUNT UNIFORMITY
1
OFF 100000
101001
1001
0.71
2
OFF 200000
200999
999
0.69
Introduction(Packages)
28
SIMSCRIPT II.5 Preamble,
Queueing
Model
1 PREAMBLE
2
PROCESSES INCLUDE ARRIVAL.GENERATOR,
3
CUSTOMER, AND REPORT
4
RESOURCES INCLUDE SERVER
5
DEFINE DELAY.IN.QUEUE, MEAN.INTERARRIVAL.TIME,
6
AND MEAN.SERVICE.TIME AS REAL VARIABLES
7
DEFINE TOT.DELAYS AS AN INTEGER VARIABLE
8
DEFINE MINUTES TO MEAN UNITS
9
TALLY AVG.DELAY.IN.QUEUE AS THE AVERAGE AND
10
NUM.DELAYS AS THE NUMBER OF DELAY.IN.QUEUE
11
ACCUMULATE AVG.NUMBER.IN.QUEUE AS THE
12
AVERAGE OF N.Q.SERVER
13
ACCUMULATE UTIL.SERVER AS THE AVERAGE OF
14
N.X.SERVER
15 END
Introduction(Packages)
29
SIMSCRIPT II.5 Main program
Queueing Model
1 MAIN
2
3
READ MEAN.INTERARRIVAL.TIME,
4
MEAN.SERVICE.TIME, AND TOT.DELAYS
5
6
CREATE EVERY SERVER(1)
7
LET U.SERVER(1) = 1
8
9
ACTIVATE AN ARRIVAL.GENERATOR NOW
10
11
START SIMULATION
12
13 END
Introduction(Packages)
30
SIMSCRIPT II.5 Process routine
ARRIVAL.GENERATOR
1 PROCESS ARRIVAL.GENERATOR
2
3
WHILE TIME.V >= 0.0
4
DO
5
WAIT EXPONENTIAL.F(MEAN.INTERARRIVAL.TIME,
6
1) MINUTES
7
ACTIVATE A CUSTOMER NOW
8
LOOP
9
10 END
Introduction(Packages)
31
SIMSCRIPT II.5 Process routine
CUSTOMER
1 PROCESS CUSTOMER
2
3
DEFINE TIME.OF.ARRIVAL AS A REAL VARIABLE
4
LET TIME.OF.ARRIVAL = TIME.V
5
REQUEST 1 SERVER(1)
6
LET DELAY.IN.QUEUE = TIME.V - TIME.OF.ARRIVAL
7
IF NUM.DELAYS = TOT.DELAYS
8
ACTIVATE A REPORT NOW
9
ALWAYS
10
WORK EXPONENTIAL.F (MEAN.SERVICE.TIME, 2)
11
MINUTES
12
RELINQUISH 1 SERVER(1)
13
14 END
Introduction(Packages)
32
SIMSCRIPT II.5 Process routine
REPORT
1 PROCESS REPORT
2
3
PRINT 5 LINES THUS
SIMULATION OF THE M/M/1 QUEUE
9
PRINT 8 LINES WITH MEAN.INTERARRIVAL.TIME,
10
SERVICE.TIME, AND TOT.DELAYS THUS
MEAN INTERARRIVAL TIME
MEAN SERVICE TIME
NUMBER OF CUSTOMERS
Introduction(Packages)
**.**
**.**
*****
33
SIMSCRIPT II.5 Process routine
REPORT(Continued)
19
20
21
PRINT 8 LINES WITH AVG.DELAY.IN.QUEUE,
AVG.NUMBER.IN.QUEUE(1), ANDUTIL.SERVER(1)
THUS
AVERAGE DELAY IN QUEUE
AVERAGE NUMBER IN QUEUE
SERVER UTILIZATION
29
30
31
***.**
***.**
*.**
STOP
END
Introduction(Packages)
34
SIMSCRIPT II.5 Output Report
Queueing
Model
SIMULATION OF THE M/M/1 QUEUE
MEAN INTERARRIVAL TIME
MEAN SERVICE TIME
1.00
.50
NUMBER OF CUSTOMERS
1000
AVERAGE DELAY IN QUEUE
.43
AVERAGE NUMBER IN QUEUE
.43
SERVER UTILIZATION
.50
Introduction(Packages)
35
SLAM II network for
single-server queue simulation
EXPON(4,5)
0
0.
RNORM (3.2, 0.6)
1
1
CREATE node
QUEUE node
Introduction(Packages)
1000
1
ACTIVITY
TERMINATE node
36
SLAM II Model of
Single-Server Queue
GEN, BANKS CARSON, NELSON SINGLE SERVER QUEUE EXAMPLE, 1/20/95
LIMITS,1,0,30; MODEL CAN USE 1 FILE, MAX NO. OF SIMULTANEOUS ENTRIES 30
NETWORK;
BEGINNING OF MODEL
CREATE, EXPON(4.5)
CUSTOMERS ARRIVE AT CHECKOUT
QUEUE(1);
CUSTOMERS WAIT FOR SERVICE IN
QUEUE FILE ONE (1)
ACTIVITY(1)/1,RNORM(3.2,.6);
CHECKOUT SERVICE TIME IS N(3.2,0.6)
TERMINATE, 1000;
SIMULATE UNTIL 1000 CUSTOMERS
ARE CHECKED OUT
ENDNETWORK;
END OF MODEL
END OF SIMULATION
Introduction(Packages)
37
CSIM Sample Code(1)
/* simulate an M/M/1 queue
(an open queue with exponential service times and interarrival
intervals)
*/
#include "lib/csim.h"
#define SVTM
#define IATM
#define NARS
FACILITY f;
EVENT done;
TABLE tbl;
QTABLE qtbl;
int cnt;
1.0
2.0
5000
/*mean of service time distribution */
/*mean of inter-arrival time distribution */
/*number of arrivals to be simulated*/
/*pointer for facility */
/*pointer for counter */
/*pointer for table */
/*pointer for qhistogram */
/*number of active tasks*/
Introduction(Packages)
38
CSIM Sample Code(2)
sim()
{
int i;
set_model_name("M/M/1 Queue");
create("sim");
/*1st process - named sim */
/*required create statement*/
f = facility("facility");
done = event("done");
tbl = table("resp tms");
qtbl = qhistogram("num in sys", 10);
/*declare facility*/
/*declare event*/
/*declare table */
/*declare qhistogram*/
cnt = NARS;
for(i = 1; i <= NARS; i++) {
hold(expntl(IATM));
cust();
}
wait(done);
report();
theory();
/*initialize cnt*/
/* hold interarrival*/
/*initiate process cust*/
/*wait until all done*/
/*print report*/
/*print theoretical res*/
}
Introduction(Packages)
39
CSIM Sample Code(3)
cust()
{
float t1;
create("cust");
statement*/
/*process customer*/
/*required create
t1 = clock;
note_entry(qtbl);
reserve(f);
hold(expntl(SVTM));
release(f);
record(clock-t1, tbl);
note_exit(qtbl);
cnt--;
if(cnt == 0)
set(done);
/*time of request */
/*note arrival */
/*reserve facility f*/
/*hold service time*/
/*release facility f*/
/*record response time*/
/*note departure */
/*decrement cnt*/
/*if last arrival, signal*/
}
Introduction(Packages)
40
CSIM Sample Code(4)
theory()
/*print theoretical results*/
{
float rho, nbar, rtime, tput;
printf("\n\n\n\t\t\tM/M/1 Theoretical Results\n");
tput = 1.0/IATM;
rho = tput*SVTM;
nbar = rho/(1.0 - rho);
rtime = SVTM/(1.0 - rho);
printf("\n\n");
printf("\t\tInter-arrival time
printf("\t\tService time
printf("\t\tUtilization
printf("\t\tThroughput rate
printf("\t\tMn nbr at queue
printf("\t\tMn queue length
printf("\t\tResponse time
printf("\t\tTime in queue
=
=
=
=
=
=
=
=
%10.3f\n",IATM);
%10.3f\n",SVTM);
%10.3f\n",rho);
%10.3f\n",tput);
%10.3f\n",nbar);
%10.3f\n",nbar-rho);
%10.3f\n",rtime);
%10.3f\n",rtime - SVTM);
}
Introduction(Packages)
41
CSIM Results(1)
Tue Dec
1 09:25:18 1987
CSIM Simulation Report Version 12
Model: M/M/1 Queue
Time:
Interval:
CPU Time:
10041.661
10041.661
32.183 (seconds)
Facility Usage Statistics
+----------------------+---------------means----------------+---counts----+
facility
srv
disp serv_tm
util
tput
qlen
resp
cmp
pre
facility
0.992
0.494
0.5
Introduction(Packages)
0.991
1.989
5000
0
42
CSIM Results(2)
Table 1
Table Name: resp tms
mean
variance
1.989
3.813
min
max
0.000
14.273
Number of entries 5000
QTable 2
QTable Name: num in sys
Mean queue length
Mean time in queue
0.991
1.989
Max queue length
Number of entries
Introduction(Packages)
13
5000
43
CSIM Results(3)
Queue Table Histogram
Length % of Elapsed Time
0
0.506
1
0.242
2
0.123
3
0.067
4
0.035
5
0.015
6
0.007
7
0.002
8
0.001
9
0.001
10
0.000
over
0.001
Cumulative
0.506
0.748
0.871
0.938
0.972
0.988
0.995
0.997
0.998
0.999
0.999
1.000
Introduction(Packages)
Count
2516
3694
1845
1014
510
234
99
40
21
13
6
8
Mean Time
2.020
0.657
0.671
0.659
0.686
0.652
0.700
0.627
0.469
0.823
0.519
0.807
44
CSIM Results(4)
M/M/1 Theoretical Results
Inter-arrival time
Service time
Utilization
Throughput rate
Mn nbr at queue
Mn queue length
Response time
Time in queue
=
=
=
=
=
=
=
=
2.000
1.000
0.500
0.500
1.000
0.500
2.000
1.000
Introduction(Packages)
45