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> shops shops ==> [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 available jshell> 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.empty jshell> shops shops ==> [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() $.. ==> 1 jshell> pair.second() $.. ==> "one" jshell> Pair<Long,Long> pair = Pair.of(0L, 100L); jshell> pair.first() $.. ==> 0 jshell> pair.second() $.. ==> 100 jshell> /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 ==> DummyEvent
jshell> e.execute(new Shop(1))
$.. ==> Pair@........
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 customer jshell> 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 1 jshell> // one busy server with no waiting customer jshell> 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 1 jshell> // one busy server with waiting customer jshell> 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 leaves jshell> /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 times From 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 Lazy… The following is a sample run of the program. Note that inputs are passed as command line arguments toΒ Main.
|
|||
Level 4Implement the customer queues Input 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 breaks Input 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 counters Input 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 customers Input 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.
|
