Requirements
- Immutability
- Pure Functions
- Randomizing the arrival and service times
- Object-oriented design with possibly a mix of imperative/declarative (functional) implementations
- Program style: adherance to CS2030 Java Style Guide
- Java documentation: adherence to CS2030 Javadoc Specification
Problem Description
This stage of the project comprises three parts:
- Dealing with side-effects
- Randomizing arrival and service times
- More complex behavior of shops, servers, and customers
Dealing with Side-Effects
For this part of the project, we shall first tackle the issue of side effects in Project #1. You would probably have coded something similar to the following, when processing the different Events (arrive, serve, wait, leave, done, ) in the PriorityQueue pq.
while (!pq.isEmpty()) { Event e; e = pq.poll(); System.out.println(e); Event nextEvent = e.execute(); if (nextEvent.isValidEvent()) { pq.add(nextEvent); } }
Notice that every time the execute method of an event is invoked, it not only generates the next event based on the status of the Servers (here we call it a Shop), it will actually change the status of the servers as a side-effect. As such, we would like to address this side-effect by re-defining event generation as follows:
e.execute(s) -> (e',s')
That is to say, the invocation of the execute method of an Event e with the argument Shop s, would now generate the next Event e' and Shop s' as a pair of values. In a similar fashion, e'and s' can then be used to generate the next pair of values.
Randomized Arrival and Service Time
Rather than fixed arrival and service times, we will generate random times. A random number generator is an entity that generates one random number after another. Since it is not possible to generate a truly random number algorithmically, pseudo random number generation is adopted instead. A pseudo-random number generator can be initialized with a seed, such that the same seed always produces the same sequence of (seemingly random) numbers.
Although, Java provides a class java.util.Random, an alternative RandomGenerator class that is more suitable for discrete event simulation is provided for you that encapsulates different random number generators for use in our simulator. Each random number generator generates a different stream of random numbers. The constructor for RandomGenerator takes in three parameters:
- int seed is the base seed. Each random number generator uses its own seed that is derived from this base seed;
- double lambda is the arrival rate, ;
- double mu is the service rate, .
The inter-arrival time is usually modeled as an exponential random variable, characterized by a single parameter denoting the arrival rate. The genInterArrivalTime() method of the class RandomGenerator is used for this purpose. Specifically,
- start the simulation by generating the first customer arrival event with timestamp 0
- if there are still more customers to simulate, generate the next arrival event with a timestamp of T + now, where T is generated with the method genInterArrivalTime();
The service time is modeled as an exponential random variable, characterized by a single parameter, service rate . The method genServiceTime() from the class RandomGenerator can be used to generate the service time. Specifically,
- each time a customer is being served, a DONE event is generated and scheduled;
- the DONE event generated will have a timestamp of T + now, where T is generated with the method genServiceTime().
You may refer to the API of the RandomGenerator class here. The class file can be downloaded from here.
Note that RandomGenerator class resides in the cs2030.simulator package. So, RandomGenerator.class should be saved in the cs2030/simulator directory.
More Complex Behaviour of Shops, Serves and Customers
You will extend the simulator to model the following entities.
- FIFO (first-in-first-out) queues for customers with a given maximum capacity
- Two new events
- SERVER_REST that simulates a server taking a rest, and
- SERVER_BACK that simulates a server returning back from rest
- Two types of servers,
- human servers who may rest after serving a customer, and
- self-checkout counters that never rest
- Two types of customers
- typical customers that joins the first queue (scanning from server 1 onwards) that is still not full, and
- greedy customers that joins the queue with the fewest waiting customers
Customer Queues
Each human server now has a queue of customers to allow multiple customers to queue up. A customer that chooses to join a queue joins at the tail. When a server is done serving a customer, it serves the next waiting customer at the head of the queue. Hence, the queue should be a first-in-first-out (FIFO) structure. The self-checkout counters, however, have only a single shared queue.
Taking a Rest
The human servers are allowed to take occasional breaks. When a server finishes serving a customer, there is a probability Pr that the server takes a rest for a random amount of time Tr. During the break, the server does not serve the next waiting customer. Upon returning from the break, the server serves the next customer in the queue immediately.
To implement this behavior, introduce two new events, SERVER_REST and SERVER_BACK, to simulate taking a break, and returning. These events should be generated and scheduled in the simulator when the server decides to rest.
Self-Checkout
To reduce waiting time, self-checkout counters have been set-up. These self-checkout counters never need to rest. Customers queue up for the self-checkout counters in the same way as human servers. There is one shared queue for all self-checkout counters.
Customers Choice of Queue
As before, when a customer arrives, he or she first scans through the servers (in order, from 1 to k) to see if there is an idle server (i.e. not serving a customer and not resting). If there is one, the customer will go to the server to be served. Otherwise, a typical customer just chooses the first queue (while scanning from servers 1 to k) that is still not full to join. However, other than the typical customer, a greedy customer is introduced that always joins the queue with the fewest customers. In the case of a tie, the customer breaks the tie by choosing the first one while scanning from servers 1 to k.
If a customer cannot find any queue to join, he/she will leave the shop.
All classes dealing with the simulation should now reside in the cs2030.simulator package, with the Main class outside the package, but importing the necessary classes from the package.
Program Style
Check for styling errors by invoking checkstyle. For example, to check styling for all java files
$ java -jar checkstyle-8.2-all.jar -c cs2030_checks.xml *.java
Writing and Generating Javadoc
You are to document your classes and methods with Javadoc comments. For more details, see the javadoc guide.
The Task
This task is divided into several levels. As the levels get progressively more complex, specific details will be provided in the corresponding levels.
As usual, you will need to keep track of the following statistics:
- the average waiting time for customers who have been served
- the number of customers served
- the number of customers who left without being served
Take note of the following assumptions:
- There is no longer an upper bound for the number of customers;
- The format of the input is always correct;
- Output of a double value, say d, is to be formatted with String.format("%.3f", d);
You have to complete ALL levels.
Level 1Levels 1 and 2 are specified with very rigid requirements, primarily so that students can meet the desired learning outcomes for the project. Do not worry if your code is packaged in cs2030.simulator. CodeCrunch will ignore the packages when testing in JShell.First, we shall implement an immutable Shop class to hold the Servers. Recall that our Server class is defined as follows: class Server { ... Server(int identifier, boolean isAvailable, boolean hasWaitingCustomer, double nextAvailableTime) { ... }}
The Shop class is to be developed using a very functional style. Hence no loops are allowed. Do not write explicit for-loops or while-loops or recursion; you may use implicit loops such as Java streams. jshell> new Shop(2)$.. ==> [1 is available, 2 is available]jshell> Shop shops = new Shop(List.of(new Server(1, true, false, 0), new Server(2, false, false, 1.0)))jshell> shopsshops ==> [1 is available, 2 is busy; available at 1.000]jshell> shops.find(x -> x.isAvailable())$.. ==> Optional[1 is available]jshell> new Shop(2).find(x -> x.isAvailable())$.. ==> Optional[1 is available]jshell> shops.find(x -> x.isAvailable()).ifPresent(System.out::println)1 is availablejshell> Server s = new Server(1, false, false, 2.0)jshell> shops.replace(s)$.. ==> [1 is busy; available at 2.000, 2 is busy; available at 1.000]jshell> shops.replace(s).find(x -> x.isAvailable())$.. ==> Optional.emptyjshell> shopsshops ==> [1 is available, 2 is busy; available at 1.000]jshell> /exit |
|||
Level 2Before proceeding to the Event class, you will first need to implement a generic Pair<T,U> class. This class is useful when returning multiple values from a function. jshell> Pair<Integer,String> pair = Pair.of(1, "one");jshell> pair.first()$.. ==> 1jshell> pair.second()$.. ==> "one"jshell> Pair<Long,Long> pair = Pair.of(0L, 100L);jshell> pair.first()$.. ==> 0jshell> pair.second()$.. ==> 100jshell> /exit As for the Event class, previously we created different events by overridding the execute method in Event. Rather than substitution via overriding, we shall use substitution via lambdas!The Event class is now required to have a property of type Function<Shop, Pair<Shop, Event>>. Different types of events shall assign this lambda to a different functionality. For example, suppose we have a DummyEvent defined with a functionality that takes in a Shop comprising some Servers, and creates an empty shop and another dummy event. So DummyEvent will be defined as follows (here we assume that the Event has a constructor that only takes a Function as argument): class DummyEvent extends Event { DummyEvent() { super(x -> new Pair<Shop,Event>(new Shop(), new DummyEvent())); } @Override public String toString() { return "DummyEvent"; }}jshell> Event e = new DummyEvent()e ==> DummyEventjshell> e.execute(new Shop(1))$.. ==> [email protected]jshell> e.execute(new Shop(1)).first()$.. ==> []jshell> e.execute(new Shop(1)).second()$.. ==> DummyEvent
Notice that the execute method of the Event class can be defined simply as: final Pair<Shop, Event> execute(Shop shop) { // declared final to avoid overriding return this.func.apply(shop); // func is the Function property}
Invoking execute with a Shop will result in a Pair comprising a Shop (which is empty), and another DummyEvent. As you can see, other than Event itself, all specific types of events arrive, serve, wait, done and leave, can now be fully specified with their relevant properties, and the addition of only one toString() method. Note that this constraint shall be enforced during grading. You still have the liberty of constructing your Event class in any way you wish.With this, you can now test the behaviour and correctness of your events by passing in a Shop and checking the returned Pair. Below is a snippet of how arrival events can be tested. jshell> // one available server with no waiting customerjshell> new ArriveEvent(new Customer(1, 1.0)).execute(new Shop(List.of(new Server(1,true,false,0)))).first() // (*) will not be tested$.. ==> [1 is available]jshell> new ArriveEvent(new Customer(1, 1.0)).execute(new Shop(List.of(new Server(1,true,false,0)))).second() // (*) will not be tested$.. ==> 1.000 1 served by server 1jshell> // one busy server with no waiting customerjshell> new ArriveEvent(new Customer(1, 1.0)).execute(new Shop(List.of(new Server(1,false,false,1.0)))).first()$.. ==> [1 is busy; available at 1.000]jshell> new ArriveEvent(new Customer(1, 1.0)).execute(new Shop(List.of(new Server(1,false,false,1.0)))).second()$.. ==> 1.000 1 waits to be served by server 1jshell> // one busy server with waiting customerjshell> new ArriveEvent(new Customer(1, 1.0)).execute(new Shop(List.of(new Server(1,false,true,2.0)))).first()$.. ==> [1 is busy; waiting customer to be served at 2.000]jshell> new ArriveEvent(new Customer(1, 1.0)).execute(new Shop(List.of(new Server(1,false,true,2.0)))).second()$.. ==> 1.000 1 leavesjshell> /exit Note that an arrival event does not cause the servers in the shop to change, but only transits to another event depend on the state of the servers.(*) This test case will not be tested as it is not deterministic. In the case if the server rests (level 5) in between the arrival and serve events, then the server will actually not be able to serve.Just remember the following constraints:
As there could be varying ways in how your specific events are constructed, there will be no test cases. That said, you should still test out this new implementation of event generation on the inputs of the final level of Project #1 and check if the behaviour is the same. |
|||
Level 3Randomizing arrival and service timesFrom this level on, we shall test your implementation with the Main class. Make sure that all other classes reside in the cs2030.simulator package.Input to the program comprises (in order of presentation):
Remember to start the simulation by generating the first customer arrival event with timestamp 0, and then generate the next arrival event of the next customer by adding the time generated using the method genInterArrivalTime() from the class RandomGenerator.The method genServiceTime() from the class can be used to generate the service time. Intuitively, the service time ought to be generated together with the arrival time as each customer is created before the simulation starts. However, do note that the nth customer to arrive might not be the nth customer to be served! So service time should be generated when the customer is being served, which might entail passing the RandomGenerator along with the Customer. This need not be so! Hint: Think LazyThe following is a sample run of the program. Note that inputs are passed as command line arguments to Main.
|
|||
Level 4Implement the customer queuesInput to the program comprises (in order of presentation):
Now, each queue has a maximum capacity Qmax, and a customer cannot join a queue that is full. Note that a customer being served is not inside the queue. When a customer arrives and all the queues are full, then the customer leaves.Clearly, if Qmax = 1, then the simulation reverts back to the one that allows only one waiting customer.The following is a sample run of the program.
Notice that the number of command line inputs is different from the previous level, as well as subsequent ones. In your Main class, you will need to identify the number of inputs, so as parse the inputs correctly for the correct level. |
|||
Level 5Implementing server breaksInput to the program comprises (in order of presentation):
Include two events SERVER_REST and SERVER_BACK, to simulating taking a break, and returning. These events should be generated and scheduled in the simulator when the server decides to rest.To decide if the server should rest, a random number uniformly drawn from [0, 1] is generated using the RandomGenerator method genRandomRest(). If the value returned is less than Pr, the server rests with a SERVER_REST event generated. Otherwise, the server does not rest but continues serving the next customer.As soon as the server rests, a random rest period Tr is generated using the RandomGenerator method genRestPeriod(). This variable is an exponential random variable, governed by the resting rate, . A SERVER_BACK event will be scheduled at Tr + now.The following is a sample run of the program.
|
|||
Level 6Include self-checkout countersInput to the program comprises (in order of presentation):
There are Nself self-checkout counters set up. In particular, if there are k human servers, then the self-checkout counters are identified from k + 1 onwards. All self-checkout counters share the same queue. When we print out the wait event, we always say that the customer is waiting for the self-checkout counter k + 1, even though this customer may eventually be served by another self-checkout counter.The following is a sample run of the program.
|
|||
Level 7Include greedy customersInput to the program comprises (in order of presentation):
An arriving customer is a greedy customer with probability Pg. To decide whether a typical or greedy customer is created, a random number uniformly drawn from [0, 1] is generated with the RandomGenerator method genCustomerType(). If the value returned is less than Pg, a greedy customer is generated, otherwise, a typical customer is generated.The following is a sample run of the program.
|
Reviews
There are no reviews yet.