Scientific Programming II

ModSim

Unit 3 - Assignment

Problem 1

Implement the supermarket simulation by using the following algorithm:

Generate a random integer between 1 and 4 to represent the arrival time of the first customer.
Generate a random integer between 1 and 5 to and add it to the value in Step 1 to represent the departing time of the first customer. The difference between the arrival time and the departing time for a customer will represent the total wait time (time waiting in the line + processing time at the check-out counter) for that customer.
Print a line stating when the first customer will arrive and depart (see example below).
Run the simulation for 2 hours. A for loop from 0 to 120 will represent the time elapsed. Each value in loop represents the time duration of one minute. Practically speaking, the (for) loop represents the clock.
For every value in the (for) loop:
- Check to see if the arrival time of a customer has been reached. If yes, add this customer to the back of the line represented by the linked list and print a line stating the customer has arrived (specify the customer#). Further, randomly generate a number between 1 and 4 and add that to the value in the (for) loop and assign it to the variable which represents the arrival time of the next customer. Print a line stating the arrival time of the next customer (specify the customer#).
- Check to see if the departure time of a customer has been reached. If yes, check to see if the queue is empty.
  - If the queue is not empty, print a line stating that the customer will be departing (specify the customer #). Remove this customer from the front of the line represented by the linked list.
  - Randomly generate a number between 1 and 5 and add that to the value in the (for) loop and assign it to represent the departure time of the next customer. Print a line stating the departure time of the next customer (specify the customer#).
- Print the line after every value in the (for) loop to display the customers standing in the line.

Important Note - Synchronization

Since the arrival and departure rates are random, the arrival and departure for the same customer will not be properly synchronized. That is, at times, the time value for departure may be less than or equal to the time value for arrival. In our simulation, this will probably happen for about 3-5 customers (as the random values for the arrival times have a lower range compared to the random values of departure times). We will deal with synchronization in more detail when we discuss Multithreading in Java later in the course. For this problem, we will ignore this scenario.

Output

Supermarket Simulation
Arrival Time of Customer#1 = 2
Departure Time of Customer#1 = 7

The Clock = 0 seconds
No Customers

The Clock = 1 seconds
No Customers

The Clock = 2 seconds
Customer 1 has arrived
Arrival Time of Customer#2 = 6
Line: 1

The Clock = 3 seconds
Line: 1

The Clock = 4 seconds
Line: 1

The Clock = 5 seconds
Line: 1

The Clock = 6 seconds
Customer 2 has arrived
Arrival Time of Customer#3 = 10
Line: 1 --> 2

The Clock = 7 seconds
Customer 1 departs
Departure Time of Customer#2 = 9
Line: 2

The Clock = 8 seconds
Line: 2

The Clock = 9 seconds
Customer 2 departs
Departure Time of Customer#3 = 14
No Customers

The Clock = 10 seconds
Customer 3 has arrived
Arrival Time of Customer#4 = 11
Line: 3

The Clock = 11 seconds
Customer 4 has arrived
Arrival Time of Customer#5 = 15
Line: 3 --> 4

...

The Clock = 100 seconds
Customer 37 has arrived
Arrival Time of Customer#38 = 103
Line: 29 --> 30 --> 31 --> 32 --> 33 --> 34 --> 35 --> 36 --> 37

...

The Clock = 117 seconds
Customer 45 has arrived
Arrival Time of Customer#46 = 120
Line: 36 --> 37 --> 38 --> 39 --> 40 --> 41 --> 42 --> 43 --> 44 --> 45

The Clock = 118 seconds
Line: 36 --> 37 --> 38 --> 39 --> 40 --> 41 --> 42 --> 43 --> 44 --> 45

The Clock = 119 seconds
Line: 36 --> 37 --> 38 --> 39 --> 40 --> 41 --> 42 --> 43 --> 44 --> 45

The Clock = 120 seconds
Customer 46 has arrived
Arrival Time of Customer#47 = 123
Customer 36 departs
Departure Time of Customer#37 = 124
Line: 37 --> 38 --> 39 --> 40 --> 41 --> 42 --> 43 --> 44 --> 45 --> 46

Solution

import java.util.Random;

public class SupermarketLine
{
    public static void main(String[] args)
    {
        System.out.println("Supermarket Simulation");
        Random random = new Random();
        Queue queue = new Queue();
        int arr_time = 0, dep_time = 0, id1 = 1, id2 = 1;

        arr_time = random.nextInt(4) + 1;
        dep_time = arr_time + random.nextInt(6) + 1;

        System.out.println("Arrival Time of Customer #" + id1 + " = " + arr_time);
        System.out.println("Departure Time of Customer #" + id2 + " = " + dep_time);

        for (int i = 0; i <= 120; i++) {
            System.out.println("The Clock = " + i + " seconds ");
            
            if (i == arr_time) {
                queue.enqueue(id1);
                System.out.println("Customer " + id1 + " has arrived ");
                id1++;
                arr_time = i + random.nextInt(4) + 1;
                System.out.println("Arrival Time of Customer#" + id1 + " = " + arr_time);
            }

            if (i == dep_time && !queue.isEmpty()) {
                System.out.println ("Customer# " + id2 + " departs");
                queue.dequeue();
                id2++;
                dep_time = i + random.nextInt(5) + 1;
                System.out.println ("Departure Time of Customer#" + id2 + " = " + dep_time);
            }
        }
        System.out.println("Line: " + queue.toString()); 
    }
}

Problem 2

A priority queue is a queue in which elements are assigned a priority, and only dequeued according to that priority. Therefore, elements with higher priority are dequeued first. Write a class PriorityQueue that implements this data structure.

One implementation is to use an array of Queue structures, with the array index being the priority. Elements of priority 0 are stored in array[0], and so on. En- and dequeuing are slightly different from a normal queue, however.

Enqueued items are added to the end of the Queue located at array[priority]
When dequeue is called, the array of Queue structures is traversed backwards (from highest to lowest priority), and the first non-empty Queue has an element dequeued.

Make life easy, and use 0-9 as your priorities.