An Application of ADT Queue: Simulation

Tom Kelliher, CS23

Apr. 2, 1996

Simulation

A technique for modeling the behavior of natural and man-made systems. Useful for summarizing the performance of existing systems or predicting the performance of proposed systems.

• Event: ``Something'' scheduled to happen.
• Event list: ``To do'' list.
• The notion of time in simulation: Event driven simulation.
• Obtaining good input data.
• Correctly modeling the system.
• Interpreting the results.

A Banking Example

Customers at the First National Bank of Avarice are complaining of having to wait too long in line. What should the bank president, Mon E. Baggs, do:

• Continue serving customers with one teller?
• Use three tellers with three lines?
• Use three tellers with a single line?

What is our data?

What do we measure?

Data file is ordered pairs:

1. Arrival time.
2. Service time.

Assumptions:

1. Upon arrival, customer immediately enters (shortest) teller line.
2. When teller and customer finish:
   • Customer immediately leaves.
   • Next customer immediately begins service.

Attributes of an event:

1. Time of occurrence.
2. Activity, if any, to trigger.

What kinds of events:

1. Arrival event: Get next arrival event. Additional information: service time.
2. Departure event: Service next customer, accumulate statistics.

From arrival event to departure event: where are the waiting customers?

What we need to keep track of:

1. Time.
2. Waiting customers.
3. Events. (How many?)
4. Input data.
5. Statistics.

What ADTs can we use/do we need?

Is there a hierarchy to these ADTs?

How does it fit together?

Implementation Detail

Customer arrives and enters empty line. Can customer immediately go to teller?

Simulation situation: Moving event from a queue to the event list.

1. Suppose event moved from queue when it's moved to event list.

2. Suppose event moved from queue when it's removed from event list.

Programming Project

Event flow:

Associated with event:

1. Name.

2. Transaction type.

3. Payment form.

4. Arrival time.

5. Event.

6. Event time.

Needed data structures:

1. Queue.

2. Sorted linked list (keyed on name).

3. Sorted linked list (keyed on event time).

Pseudocode:

open arrival file;
set time to 0;
initialize statistics;
put first arrival on event list;

while there's an event
   get next event;
   advance time;
   cause event;
   print message;
   accumulate statistics;

print final statistics;
close arrival file

Example event: sign-in

remove event from sign-in queue;
if event's transaction type is license renewal
   putInLicenseList();
else
   putInRenewalQueue();

if sign-in queue isn't empty
   create new sign-in event (event time is current time + 10s.);
   insert event in event queue;

putInLicenseList():

if license list is empty
   create new license event (event time is current time + 90s);
   insert event in event queue;
else
   insert entry in license list;

Walk through some data (sanity testing):

1. License, cash, 0 sec.

2. Registration, check, 0 sec.

3. Combination:
   1. License, cash, 0 sec.

   2. Registration, check, 10 sec.