University of Toronto
Department of Computer Science
CSC148H, Summer 2007



Assignment 3:   (Due July 14 @ 9am)


Introduction

In this assignment, you are asked to develop a simulation of processes that take place in an airport. You will build an object-oriented model of the airport in Java, and then run it in order to gather interesting statistics about the efficiency of the associated processes. Part of the deliverable code is given to you to reuse as-is or with changes of your choice.

The goals of the assignment are a) to understand the basics of event-driven simulation, b) to exercise your programming skills with queues and arraylists, c) to gain experience in reading and understanding existing code and integrating/adapting it with the part that you will develop.

In the rest of this document we will look at: We will also provide a few comments on how you can use the starter code to achieve these objectives.

The Airport with flights to Wonderland

For this simulation you are going to model the Departures section of an Airport terminal. The particular terminal is dedicated to flights to Wonderland, a nearby country and very popular holiday destination. Passengers that arrive at this terminal are either Wonderland citizens or foreigners that want to visit Wonderland. In order to reach the gate and board the airplane that will take them to Wonderland, passengers need to check-in, pass through security control and, if they are not citizens of Wonderland, they also need to pass through a customs control. Here are these steps in more detail.

Check-In: The first thing that a passenger needs to do, once she arrives at the terminal, is to check-in. To allow checking-in, the airline designates a number of counters, say N, numbered (indexed) from 1 to N, in which their employees validate the passenger's ticket and provide them with a boarding pass. If the passenger arrives, several such counters are free, and there is nobody waiting in line, she goes to the one with the smallest index. So, for example, if check-in counters 2 and 4 are free, she goes to 2. If a passenger arrives and all check-in counters are busy serving other passengers, then she enters a queue, and waits for her turn. The queue is one for all counters.

>From a check-in employee point of view, once he is done with a passenger, he checks to see if the queue is empty. If it is empty he sits back and relax. If it is not he calls for the next person in line.

Security: Once the passenger has checked-in and obtained her boarding pass, she may now move towards the gate, where she will board the aircraft. To reach that area, however, she needs to pass through security control. This consists of a number of gates, again indexed from 1 to M, each attended by a security staff member. The process is very similar to the check-in: when passengers arrive they choose the free security gate with the smallest index (provided no-one waits in the queue); if none is free they wait in the security queue (there is one queue shared by all security gates). Once a security staff has finished searching one person, he calls the first person in the security queue, or sits down and gets a sip of tea if the queue is empty.

Customs: After having subjected our poor passenger to two potentially long waiting lines, should we now leave her alone? Of course not! She has to pass the customs, if she is not a citizen of Wonderland. Thus, there is yet another array of counters where she is checked by security and customs officials. Again, the structure and process is exactly the same as check-in and security, so we omit a description. But, note that if she is a citizen of Wonderland then, once she is done with the security process, she skips customs and just goes straight to the boarding gate where she can enjoy a cup of coffee, while waiting for the gate to open (and the non-citizens to arrive tired and obviously annoyed!).

There are many other processes that take place in this context (e.g. what happens to luggage or what happens after passengers arrive at the gate?). But we are not interested in these here. Indeed, when we develop models for simulation or for other purposes, we are usually interested just in some aspects of the real phenomena.

Notice that there are four parameters that are interesting when we want to simulate our airport. One is the average distance between arrivals. The other three are the (different) average service times for each of the check-in, security control, and customs-check processes. We will return to these below.


Developing a Simulation Program: Events and Queues

While real-time simulations are useful for some applications, here we are interested in an event-driven simulation, a type of simulation that focuses only on the occurrence of certain phenomena in the real world. Thus, we are interested in significant events, not what happens between their occurrences. In the event-based simulation all we do is to schedule events and, meanwhile, run a loop that goes through the scheduled events and picks the one that will happen next. This event, in turn, may imply that we need to schedule a new event. For example, the event that our passenger is accepted at a security gate implies that we should schedule her departure from the security queue, within a time period more or less equal to the average service time at a security gate.

How do we implement this type of scheduling and picking-up of events in Java? We typically use a priority queue. Such a data structure dequeues items in the order of some number, the priority number. In our case, the priority queue consists of a diversity of event objects and the priority number attached to each one of them is the time they are supposed to occur. The order by which we schedule events is not necessarily the same order by which they should occur. For example, you may expect that a check-in counter will finish serving the passenger at time t=3400 (and have already scheduled this in the queue), but realize that another passenger arrives at the airport at t=3350. Obviously the event that the new passenger arrived must be considered before the event that the other passenger has finished check-in. The earlier the event will happen, the higher its priority will be, independent of when we learned about this event.

In simulation, it's traditional to call this priority queue of events the "event list", so the class you must write is EventList. EventList implements the interface PriorityQueue. We have provided you with the PriorityQueue interface and your job is to write EventList. The items to be stored in EventList are children of the class Event (we have also supplied the Event class for you). Notice that Event implements Prioritized, because PriorityQueue requires that. The Prioritized interface is also supplied for you.

The most important method in the Event class is happen(); this method carries out the actions that occur when an event takes place, and in simulation jargon the method is called an "event routine". The event routine in Event is abstract, because the actions required are only known in more specific child classes of Event.

We've given you a few lines of EventList.java that should help you see what to do. But here's one requirement you can't figure out from the code: The data structure used in EventList MUST BE a linked list. The node type must be an inner class of EventList.

Average Time Between Passenger Arrivals, Average Serving Times, and Passenger Types

If you are told that one passenger arrives at the Airport every 60 seconds on average, you don't really think that it has to be that the next passenger has to arrive exactly 60.000 seconds after the previous one, do you? Because, in reality, she may arrive after 51 seconds, or after 67.02 seconds. She may even arrive after 132.3 seconds or after 7.1 seconds, though less likely. The same is true for the service times at the check-in counters, the security and the customs: the time it takes for each passenger to be served may vary around the average. Thus, to make the simulation realistic, we need a function that takes as input a known average (e.g. 60 sec) and outputs the same average plus or minus a randomly generated offset. We have implemented that function for you and you should use it to schedule the events.

The same is true for service time in checking-in, security control, and customs control (service time doest NOT include the waiting time in the queue, and is just the time from when the counter/gate starts to sever a passenger till it finishes serving this passenger). Note that these are three different processes in nature and you should expect they exhibit different average service times.

Also, when we want to decide whether the new passenger will be a citizen of Wonderland or not we need a function that decides what passenger type she will be, based on what proportion of passengers that arrive at the airport are generally citizens of Wonderland.

We have provided class Time that maintains a central clock for the simulation and also generates random numbers of the kinds you need, as described above. We choose to use seconds to measure time. Note that, in an event-driven simulation, the central clock does not increase one second at a time! Rather, it jumps to the time when the next event is happening.

Here are some of the methods of Time (Note: you must NOT change Time class):

Gathering Statistics

We develop and run a simulation because we need to gather statistics. In the Airport case there are two types of things that we mostly want to measure: how long it takes for passengers to reach the gate as well as how much the employees at the counters/gates are busy serving passengers. The exact statistics you will need to collect will become apparent by looking at the sample output below.

The strategy is to maintain variables that we update once the appropriate events occur. You have to decide what these variables are, where they will reside and how you will update them!

Reports

There are two kinds of reports we need: the intermediate and the final. We provide the format of each of these reports below, through examples. You should follow these formats rigidly. The intermediate report shows what the current state of the airport is: how many people are waiting in each of the three queues and whether the counters and gates are busy or free. Note that the intermediate report is an event on its own, with the difference that there is no randomness in scheduling it! Here is an example with 3 check-in counters, 4 security gates and 3 customs counters:

State of the Airport:
    Time:21600.0
    Waiting to Check-In:190
    Waiting for Security:0
    Waiting to Customs:17
    State of Check-In Counters:
        1:[Busy]  2:[Busy]  3:[Busy] 
    State of Security Gates:
        1:[Busy]  2:[Free]  3:[Busy]  4:[Free] 
    State of Customs Counters:
        1:[Busy]  2:[Busy]  3:[Busy] 

Note that, in the above statistics, the number of people waiting in [Check-In/Security/Customs] does not include those that are being served. After the simulation is over the final report must be printed. Among other things, this reports the average waiting time of each passenger type (and for both types together), as well as the average waiting time at each of the three queues. In addition, the percentage of the time that each of the counters was busy serving a customer is also given.

Overall:
    Simulation Start Time:0.0
    Simulation Stop Time:28800.0
    Report interval:3600.0
    Total Passengers who Reached the Boarding Gate:134
        Total Citizens Reached the Boarding Gate:70 
        Total Visa Reached the Boarding Gate:64
    Check-In Waiting Time:1063.35
    Security Waiting Time:931.98
    Customs Waiting Time:781.14
    Average Processing Time for Citizens:2032.35
    Average Processing Time for Visitors:2783.77
    Average Processing Time for Everybody:2391.24

Per Counter/Gate: (GateID)/[Total Served]/[Percentage Busy]
    Check In Counters
        (1)/[37]/[89%]
        (2)/[54]/[87%]
        (3)/[45]/[83%]

    Security Gates
        (1)/[41]/[90%]
        (2)/[36]/[82%]
        (3)/[33]/[71%]
        (4)/[26]/[64%]
    Customs
        (1)/[27]/[68%]
        (2)/[26]/[47%]
        (3)/[11]/[28%]

"[Check-In/Security/Customs] Waiting Time" refers to the average time that passengers spend waiting in each of the corresponding queues. This time does not include service time.
"Average Processing Time for [Citizens/Visitors/Everybody]" refers to the average time that a passenger needs to reach the boarding gate. Service times are included here. For the calculation of the average only the passengers that have actually arrived at the gate are going to be considered (because, when the simulation ends there are still passengers waiting in lines etc. but you don't consider those).
"Percentage Busy" is the ratio of the total time that each counter is busy serving a passenger over the total simulation time.

Now, what you should do.

To simulate the airport you will have a class that represents the airport, classes that represent the different kinds of counters, a class representing the passengers, as well as classes that represent the relevant events. You are also required to use separate classes for keeping your statistics, when this is applicable. More specifically:

EventList

See above. You need to write nearly the entire class, and this is the class that we will autotest.

Airport

This is a central class in your implementation, and we are providing you with an initial sketch. The Airport class maintains a reference to the three queues of passengers as well as to three ArrayLists of counters/gates. There is a designated function (e.g. the constructor) that "builds" the airport according to the given parameters. These parameters are the number of check-in, security and customs counters, as well as the average service time for each. We assume that all counters/gates have the same average service time (i.e. no check-in employee is faster than the other check-in employees etc.). The average time distance between arrivals, as well as the (exact) distance between intermediate reports are also parameters of Airport that need to be instantiated.

The Airport contains methods that decide what happens when certain events happen. We have sketched two of them through comments, you need complete these and add other ones. 

CompleteCheckInEvent

This class specifies what needs to happen when Check-In is complete for a passenger. That is, it's an event class, modeling the end-of check-in process. You will need another two event classes for signifying, respectively, that security and customs' control are over for a passenger. The method happen must call the appropriate method at the Airport class, which handles subsequent enqueuing and scheduling tasks. You need to complete that method as indicated above. And, of course, you need to write all the other necessary events. They are very similar!

CheckInCounter

The class specifies objects that carry characteristics of a check-in counter including the counter index and the time it takes to serve a passenger. Upon acceptance of a new passenger the completion event must be scheduled (so you should add the appropriate line). You should also add the appropriate statistics variables. Needless to say, you will also need the SecurityGate and the CustomsCounter classes!

Passenger

The Passenger class carries the status of the passenger with respect to Citizenship in Wonderland. This is decided during construction of the class. You also need to associate the Passenger with some statistics variables.

Driver

You're not required to do anything to Driver, but you're allowed to. However, the data format needs to stay the same. The marking TA is going to give this command, working from the command line:
   java Driver < data
using various data files of our own. Note that "< data" means to read from a file called data rather than the default standard input(keyboard). We suggest you save all your input in a file and run the program as above (it will be convenient as you can easily change the file and re-run your program). Make sure that your program runs without errors on data files of the format required by the Driver class we provided.

What to Submit

  1. You must submit every class needed to make your simulation run. 
  2. You must also submit a test class, EventListTest using JUnit to test EventList. 
  3. You need to write Javadoc documentation and internal comments for all the code you write.
  4. Write a report that:
    1. provides a high level description of your design (what the main objects are and how they interact),
    2. explains how statistics are gathered,
    3. provides a rationale of five of your test cases (why you chose them).
    The report should be absolutely NO more than 800 words, and must be submitted electronically in a TXT file called Overview.txt.

To Change or Not To Change?

Here is a list of classes you ABSOLUTELY MUST NOT change, because during testing we will replace them with the original versions:


Here are the classes you are given to get you started and should complete and change as you like. As stated above you will of course have to add several other classes.

Marking Scheme