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);

}

}

}