Lecture on event simulation
A.1 server 1 queue
Events: arrivals, departure, end of simulation
Data structures needed: arrival queue, length of queue, busy signal for server, event list
Routines: arrival, departure, timing
Arrival: (1) schedule arrival of next customer-change event list
(2) If server is busy
(a) Increment number in queue
(b) Put arrival time in queue
else
(c) change busy signal to busy
(d) schedule departure of current customer and change event list
(3) increase number of customers
Departure: (1) If arrival queue is empty
(a)change server signal to idle
else
(b)decrement number in queue
(c) schedule departure of current customer and change event list
Timing: (1)Scan event list and determine the time of next event and whether event is an arrival, departure, or end of simulation.
(2) Remove the event from the eventlist
Notes- (1) arrivals are scheduled only by arrival routine- on the arrival of the previous customer
(2) Departures are scheduled when a customer is served and may be scheduled by either the arrival routine or the departure routine
(3) with 3 types of events, no need to keep list as sorted, eventlist[1] is an arrival time, eventlist[2] is a departure time
B. 2 servers- 2 queues in parallel
Events: arrival to queue 1, arrival to queue 2, departure from server 1, departure from server 2, end of simulation- 5 events.
Data structures needed: 2 arrival queues, , length of each queue , busy signal for each server, event list
Routines: arrival(queue number), departure(server number), timing
All routines do the same as in 1 queue 1 server but with a parameter to denote which queue and which server
Notes: (1)5 types of events- so still no need to keep list sorted
(2)might keep queues in a 2 dimensional array of 2 columns, and busy signal is now an array of length 2
(3) might use a separate random number stream for each arrival and departure stream- 4 streams
C 2 servers 2 queues in series- with no travel time in between
Events: arrival to queue 1, departure from server 1, departure from server 2, end of simulation- 4 events.
Data structures needed: 2 arrival queues, length of each queue ,busy signal for each server, event list
Routines: arrival(1), departure(server number), timing
arrival(1) does the same as arrival(1) in parallel queues
No arrival(2)
departure(1) adds the following activity:
(2) if the second server is not busy
a. changes the second server to busy
b. schedules departure from second server and updates event list
else
c. increases the number in queue 2
d. enters the arrival time of current job to queue 1 into proper space in queue 2
departure(2) does the same as departure(2) in parallel queues
D. 2 servers 2 queues in series- with travel time
Events: arrival to queue 1, arrival to queue 2, departure from server 1, departure from server 2, end of simulation- 5 events.
Data structures needed: 2 arrival queues, busy signal for each server, event list
Routines: arrival(queue number), departure(server number), timing
arrival(1) does the same as arrival(1) in parallel queues
arrival(2) does not schedule next arrival in the second queue
departure(1) adds the following activity:
(2) schedules the arrival to the second queue
departure(2) does the same as departure(2) in parallel queues
E. n servers- n queues in parallel
Events: arrival to each server, departure from each server, end of simulation, 2n+1 events
Data structures needed: n arrival queues, length of each queue, busy signal for each server, event list-
Routines: arrival(queue number), departure(server number), timing
All routines do the same as in 1 queue 1 server but with a parameter to denote which queue and which server
Notes: (1)2n+1 types of events-
a. If keep list sorted-
1. how many operation for search and a deletion
a. if list is saved as an array
b. if list is saved as a link list
2. How many operations for an insertion
a. if list is stored as an array
b. if list is stored as a linked list
class listlink{
public:
listlink(void);
void addtolist(float);
private:
struct node
{
float number;
struct node *next;};
struct node *head, *tail;
};
listlink::listlink(void)
{
head=new node;
tail=new node;
head->next=tail;
head->number=-1.e20;
tail->number=1.e20;
}
void linklist::addtolist(float item)
{struct node *temp, *t=head, *s=new node;
s->number=item;
while(item> t->number)
{
temp=t;
t=t->next;;
}
s->next=t;
temp->next=s;
}
(2)might keep queues in a 2 dimensional array of n columns, and busy signal is now an array of length n or keep queues as a linked list
class queuelink{
public:
queuelink(void);
void addtoqueue(float);
int deletequeue(void);
void printqueue( void );
private:
struct node
{float key; struct node *next;};
struct node *head, *tail;
};
queuelink::queuelink( void)
{
head = new node; tail = new node;
head->next=tail; tail->next=tail;
}
void queuelink::addtoqueue (float item)
{
struct node *t = new node;
tail->key=item; tail->next=t; tail =t; t->next =t;
}
int queuelink::deletequeue(void)
{
float number;
struct node *t = head->next;
number = t->key;
head->next=t->next;
delete t;
return number;
}
void queuelink::printqueue(void)
{
struct node *t= head->next;
while (t != tail)
{
cout < t->key < " ";
t = t->next;
}
cout < endl;
}
E. n servers- n queues in parallel with jockeying
Events: arrival , departure from each server, end of simulation, n+2 events
Data structures needed: n arrival queues, length of each queue, busy signal for each server, event list-
Routines: arrival, departure(server number), timing, jockey(server number)
Arrival: (1) schedule arrival of next customer-change event list
(2) increase number of customers
(3) If all servers busy
(a) Find the queue with the smallest number of customers, call it queue j
(b)Increment number in queue j
(b) Put arrival time in queue j
else
(c) change busy signal to busy for that server
(d) schedule departure of current customer and change event list
void arrive(void) /* Event function for arrival of a customer to the bank. */
{
int teller;
/* Schedule next arrival. */
event_schedule(sim_time + expon(mean_interarrival, STREAM_INTERARRIVAL),
EVENT_ARRIVAL);
/* If a teller is idle, start service on the arriving customer. */
for (teller = 1; teller <= num_tellers; ++teller) {
if (list_size[num_tellers + teller] == 0) {
/* This teller is idle, so customer has delay of zero. */
sampst(0.0, SAMPST_DELAYS);
/* Make this teller busy (attributes are irrelevant). */
list_file(FIRST, num_tellers + teller);
/* Schedule a service completion. */
transfer[3] = teller; /* Define third attribute of type-two event-
list record before event_schedule. */
event_schedule(sim_time + expon(mean_service, STREAM_SERVICE),
EVENT_DEPARTURE);
/* Return control to the main function. */
return;
}
}
/* All tellers are busy, so find the shortest queue (leftmost shortest in
case of ties). */
shortest_length = list_size[1];
shortest_queue = 1;
for (teller = 2; teller <= num_tellers; ++teller)
if (list_size[teller] < shortest_length) {
shortest_length = list_size[teller];
shortest_queue = teller;
}
/* Place the customer at the end of the leftmost shortest queue. */
transfer[1] = sim_time;
list_file(LAST, shortest_queue);
}
Departure(server number): Add jockeying at end of departure
void depart(int teller) /* Departure event function. */
{
/* Check to see whether the queue for teller "teller" is empty. */
if (list_size[teller] == 0)
/* The queue is empty, so make the teller idle. */
list_remove(FIRST, num_tellers + teller);
else {
/* The queue is not empty, so start service on a customer. */
list_remove(FIRST, teller);
sampst(sim_time - transfer[1], SAMPST_DELAYS);
transfer[3] = teller; /* Define before event_schedule. */
event_schedule(sim_time + expon(mean_service, STREAM_SERVICE),
EVENT_DEPARTURE);
}
/* Let a customer from the end of another queue jockey to the end of this
queue, if possible. */
jockey(teller);
}
Jockey(k)
If there are queues that are longer than queue(k)
a choose the queue who length is longer than queue k that is closest to queue k, call that queue m.
b. If server k is busy
1. increase the length of queue k
2. Put the last customer in queue j into queue k
3. decrease the length of queue j
else
1. make server k busy again
2. put the last customer in queue j into server k and calculate his departure and update event list
3. decrease the length of queue j
We are getting complicated - do we need a library to handle all this.
void jockey(int teller) /* Jockey a customer to the end of queue "teller" from
the end of another queue, if possible. */
{
int jumper, min_distance, ni, nj, other_teller, distance;
/* Find the number, jumper, of the queue whose last customer will jockey to
queue or teller "teller", if there is such a customer. */
jumper = 0;
min_distance = 1000;
ni = list_size[teller] + list_size[num_tellers + teller];
/* Scan all the queues from left to right. */
for (other_teller = 1; other_teller <= num_tellers; ++other_teller) {
nj = list_size[other_teller] + list_size[num_tellers + other_teller];
distance = abs(teller - other_teller);
/* Check whether the customer at the end of queue other_teller qualifies
for being the jockeying choice so far. */
if (other_teller != teller & nj > ni + 1 & distance < min_distance) {
/* The customer at the end of queue other_teller is our choice so
far for the jockeying customer, so remember his queue number and
its distance from the destination queue. */
jumper = other_teller;
min_distance = distance;
}
}
/* Check to see whether a jockeying customer was found. */
if (jumper > 0) {
/* A jockeying customer was found, so remove him from his queue. */
list_remove(LAST, jumper);
/* Check to see whether the teller of his new queue is busy. */
if (list_size[num_tellers + teller] > 0)
/* The teller of his new queue is busy, so place the customer at the
end of this queue. */
list_file(LAST, teller);
else {
/* The teller of his new queue is idle, so tally the jockeying
customer's delay, make the teller busy, and start service. */
sampst(sim_time - transfer[1], SAMPST_DELAYS);
list_file(FIRST, num_tellers + teller);
transfer[3] = teller; /* Define before event_schedule. */
event_schedule(sim_time + expon(mean_service, STREAM_SERVICE),
EVENT_DEPARTURE);
}
}
}