CS2030S-Project 1 Discrete Event Simulator Solved

A discrete event simulator is a software that simulates a system with events and states, and can be used to study many complex real-world systems such as queuing to order food at McDonald's®. An event occurs at a particular time, and each event alters the state of the system and may generate more events. States remain unchanged between two events (hence the term discrete), and this allows the simulator to jump from the time of one event to another. A simulator typically also keeps track of some statistics to measure the performance of the system.

Let us simulate a queuing system comprising only one single customer queue and single service point S as shown below.

 
The system comprises the following:

There is one server (a person providing service to the customer); the server can serve one customer at a time.
The service time (time taken to serve a customer) is constant.
When a customer arrives (ARRIVE event):if the server is idle (not serving any customer), then the server starts serving the customer immediately (SERVE event).
if the server is serving another customer, then the customer that just arrived waits in the queue (WAIT event).
if the server is serving one customer, and another customer is waiting in the queue, and a third customer arrives, then the third customer leaves (LEAVE event). In other words, there is at most one customer waiting in the queue.
When the server is done serving a customer (DONE event), the server can start serving the customer waiting at the front of the queue (if any).
If there is no waiting customer, then the server becomes idle again.
There are five events in the system, namely ARRIVE, SERVE, WAIT, LEAVE and DONE. For each customer, these are the only possible event transitions:

ARRIVE → SERVE → DONE
ARRIVE → WAIT → SERVE → DONE
ARRIVE → LEAVE
Statistics of the system that we need to keep track of are:

the average waiting time for customers who have been served
the number of customers served
the number of customers who left without being served
As an example, given the arrival times (represented as a floating point value for simplicity) of three customers with one server, and assuming a constant service time of 1.0,

0.500
0.600
0.700

the following events, each of the form <time_event_occurred, customer_id, event_details>, are produced

0.500 1 arrives
0.500 1 served by 1
0.600 2 arrives
0.600 2 waits to be served by 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 served by 1
2.500 2 done serving by 1

with the end-of-simulation statistics being respectively, [0.450 2 1].

Priority Queuing
The PriorityQueue (a mutable class) can be used to keep a collection of elements, where each element is given a certain priority.

Elements may be added to the queue with the add(E e) method. The queue is modified;
The poll() method may be used to retrieve and remove the element with the highest priority from the queue. It returns an object of type E, or null if the queue is empty. The queue is modified.
To enable PriorityQueue to order events, instantiate a PriorityQueue object using the constructor that takes in a Comparator object. For more details, refer to the Java API Specifications.

The Task
Given a set of customer arrival times in chronological order, output the discrete events. Also output the statistics at the end of the simulation.

Take note of the following assumptions:

The format of the input is always correct;
Output of a double value, say d, is to be formatted with String.format("%.3f", d);
This task is divided into several levels. Read through all the levels to see how the different levels are related.

You have to complete ALL levels.

Level 1
The Customer

Write an immutable Customer class to represent each arriving customer that is tagged with a customer ID (of type int), as well as an arrival time (of type double). You may write other accessor methods as you deem necessary.

jshell> /open Customer.java
jshell> new Customer(1, 0.5)
$.. ==> 1 arrives at 0.5
jshell> new Customer(2, 0.6)
$.. ==> 2 arrives at 0.6
jshell> new Customer(3, 0.7)
$.. ==> 3 arrives at 0.7
jshell> /exit

Level 2
The Server

Write an immutable Server class to represent a server.

class Server {
    ...
    Server(int identifier, boolean isAvailable, boolean hasWaitingCustomer, double nextAvailableTime) {
        ...
    }
}

The constructor of Server takes in four parameters:

identifier: the identifier of the server
isAvailable: whether the server is currently available to serve;
hasWaitingCustomer: while server is serving, whether there is a waiting customer;
nextAvailableTime: while server is serving, the time for the current service to finish (that is the time when the server is able to serve the next customer)
There are only three possible types of servers to be generated for testing:

new Server(i, true, anything, anything): Server #i is available; a customer that arrives can be served immediately
new Server(i, false, false, t): Server #i is busy, but with no waiting customer; i.e. it is available at time t
new Server(i, false, true, t): Server #i is busy, and with a waiting customer (to be served at time t)
jshell> /open Server.java
jshell> new Server(1, true, false, 0)
$.. ==> 1 is available
jshell> new Server(2, false, false, 0.5)
$.. ==> 2 is busy; available at 0.500
jshell> new Server(3, false, true, 1.5)
$.. ==> 3 is busy; waiting customer to be served at 1.500
jshell> /exit

Level 3
Events

Till now we have written two independent Customer and Server classes. How do we link them together? Through events!

Each event is an association between a customer and a set of servers. An event will also have the event start time, i.e. for ARRIVE events it will be the arrival time; for SERVE event it will be the time service starts; for DONE event, it will be the time the service ends, etc. All events are to be immutable.

In this level, we shall test the event transitions for an arriving customer under different Server configurations. Each test starts off with an ArrivalEvent created using the constructor that takes in the arriving customer, and the list of servers. A transition from one event to the next happens whenever the execute method is called.

$ jshell your_java_files_in_bottom-up_dependency_order
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, true, false, 0))) // server is available
$.. ==> 0.500 1 arrives
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, true, false, 0))).execute()
$.. ==> 0.500 1 served by 1
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, true, false, 0))).execute().execute()
$.. ==> 1.500 1 done serving by 1
jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))) // server is busy, but no waiting customer
$.. ==> 0.600 2 arrives
jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))).execute()
$.. ==> 0.600 2 waits to be served by 1
jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))).execute().execute()
$.. ==> 1.000 2 served by 1
jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))).execute().execute().execute()
$.. ==> 2.000 2 done serving by 1
jshell> new ArriveEvent(new Customer(3, 0.6), Arrays.asList(new Server(1, false, true, 1.0))) // server is busy with waiting customer
$.. ==> 0.600 3 arrives
jshell> new ArriveEvent(new Customer(3, 0.6), Arrays.asList(new Server(1, false, true, 1.0))).execute()
$.. ==> 0.600 3 leaves
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, false, 0), new Server(2, true, false, 0))).execute() // two servers: (1) busy; (2) free
$.. ==> 0.500 1 served by 2
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, false, 0), new Server(2, true, false, 0))).execute().execute()
$.. ==> 1.500 1 done serving by 2
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, false, 10.0))).execute() // both servers busy, (1) has waiting customer
$.. ==> 0.500 1 waits to be served by 2
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, false, 10.0))).execute().execute()
$.. ==> 10.000 1 served by 2
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, false, 10.0))).execute().execute().execute()
$.. ==> 11.000 1 done serving by 2
jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, true, 10.0))).execute() // both busy with waiting customer
$.. ==> 0.500 1 leaves
jshell> /exit

Level 4
Scheduling Events

We are finally ready to schedule events using the PriorityQueue.

As an example, consider the start of a simulation with an initial schedule of three arrival events, and only one server.

0.500 1 arrives
0.600 2 arrives
0.700 3 arrives

The next event to pick is <0.500 1 arrives>. This schedules a SERVE event.

0.500 1 served by 1
0.600 2 arrives
0.700 3 arrives

The next event to pick is <0.500 1 served>. This schedules a DONE event.0.600 2 arrives
0.700 3 arrives
1.500 1 done serving by 1

The next event to pick is <0.600 2 arrives>...This process is repeated until there are no more events.

Define a driver class Main.java that reads a series of arrival times, creates the arrival events, and starts the simulation. A skeleton class that simply reads the arrival times is given below:

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int numOfServers = sc.nextInt();

        while (sc.hasNextDouble()) {
            double arrivalTime = sc.nextDouble();
        }
    }
}

The following is a sample run of the program. User input is underlined, and starts with an integer value representing the number of servers, followed by the arrival times of the customers. Input is terminated with a ^D (CTRL-d).

You will also need to compute the statistics (see problem description above) at the end of the simulation.

 

1
0.500
0.600
0.700
^D
0.500 1 arrives
0.500 1 served by 1
0.600 2 arrives
0.600 2 waits to be served by 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 served by 1
2.500 2 done serving by 1
[0.450 2 1]

1
0.500
0.600
0.700
1.500
1.600
1.700
^D
0.500 1 arrives
0.500 1 served by 1
0.600 2 arrives
0.600 2 waits to be served by 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 served by 1
1.500 4 arrives
1.500 4 waits to be served by 1
1.600 5 arrives
1.600 5 leaves
1.700 6 arrives
1.700 6 leaves
2.500 2 done serving by 1
2.500 4 served by 1
3.500 4 done serving by 1
[0.633 3 3]
2
0.500
0.600
0.700
1.500
1.600
1.700
^D
0.500 1 arrives
0.500 1 served by 1
0.600 2 arrives
0.600 2 served by 2
0.700 3 arrives
0.700 3 waits to be served by 1
1.500 1 done serving by 1
1.500 3 served by 1
1.500 4 arrives
1.500 4 waits to be served by 1
1.600 2 done serving by 2
1.600 5 arrives
1.600 5 served by 2
1.700 6 arrives
1.700 6 waits to be served by 2
2.500 3 done serving by 1
2.500 4 served by 1
2.600 5 done serving by 2
2.600 6 served by 2
3.500 4 done serving by 1
3.600 6 done serving by 2
[0.450 6 0]
All classes dealing with the simulation should now reside in the cs2030.simulator package, with only the Main class importing the necessary classes from the package.

Compile your code using

javac -d . *.java

and run your program to ensure that everything is still in good working order.