Java: PriorityQueue - Grocery Store Simulation

Question

I've been working away at this problem for the past 10-12 hours, and was wondering if you guys could help me debug/point me in the right general direction. The object of the program is to simulate a grocery store queue-line, which I'm attempting to accomplish using:

• PriorityQueue (FIFO) data structure
• System.nanoTime() - to keep track of elapsed time
• SimpleDateFormat - to keep track of when customers enter queue (timestamp)

---

I've consulted with colleagues, on-campus tutoring services, professors and the given course textbook: "Java How To Program: Deitel & Deitel" to no avail.

The provided pseudocode for the problem is as follows (I'm not trying to get you to do it for me):

Run the supermarket simulation for a 12-hour day (720 minutes), using the following algorithm:

---

1. Choose a random integer between 1 and 4 to determine the mintue at which first customer arrives
2. At first customer's arrival time, do the following:
   • Determine the customer's service time (random integer 1 to 4)
3. Begin servicing the customer
   • Schedule arrival time of next customer (random integer 1 to 4 added to current time)
4. For each minute of the day, consider the following:
   • If the next customer arrives, proceed as follows:
   • Say so.
   • Enqueue the customer.
   • Schedule the arrival time of the next customer.
   • If the service was completed for the last customer, do the following:
     • Say so.
     • Dequeue the next customer to be serviced
     • Determine the customer's service completion time (random integer from 1 to 4 added to the current time)

The issues I'm experiencing:

1. Attempts to 'delay' program as customers arrive/are serviced are ineffective (perhaps System.nanoTime() miscalculations? (I've double checked all calculations, may still be wrong) - see: newCustomer(), serveCustomer()
2. 84983 customers at the end of 1 minute, illogical since delays of 1-4 minutes between customer arrivals (timing issue)
3. Queue never increases in size, customers are added, then removed linearly (wrong)

Note

• I have reduced the simulation time to 1 minute for testing purposes
• I cannot use a multithreaded approach to solve this problem, must be done using FIFO on single thread
• Customers arrive at intervals of 1 to 4 SECONDS, reduced for testing purposes

Here is my code:

package grocerystoresimulation;
/*
* @import
*/
import java.util.PriorityQueue;
import java.util.Random;
import java.util.ArrayList;
import java.util.Date;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
/*
* @author: Tyler J Fisher
* Date: 2/27/2012
*/
public class GroceryStoreSimulation {

/*
* @fields 
*/
private PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
private Random rand = new Random(); //instantiate new Random object    

private Date date = new Date();
private DateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd - hh:mm:ss a"); 
private ArrayList<String> timeStamp = new ArrayList<String>(); //store timestamps

private int totalCustomers; //# of customers served during simulation

private long startTime = System.nanoTime(); //time of initial build
private long simulationTime = 1; //desired time in minutes
private long firstWaitTime = generateWaitTime(); 
private long serviceCustomerAt;

/*
* @constuctor
*/
public GroceryStoreSimulation(){
    System.out.println("Instantiated new GroceryStoreSimulation @ ["
            + dateFormat.format(date) + "]\n" + insertDivider());
} //GroceryStoreSimulation()

public void run(){
    //Main program body
    try {
        Thread.sleep(firstWaitTime); //generate wait time for first customer
        System.out.println("Delay until first customer: " + firstWaitTime);
        newCustomer(totalCustomers);
        serveCustomer();
    } catch (InterruptedException e){/*Catch 'em all*/}

    while((System.nanoTime()-startTime)<=(simulationTime*60000000000L)-firstWaitTime){
        try {
            newCustomer(totalCustomers); //enque customer 
            serveCustomer();
        } catch(Exception e){/*Catch 'em all*/}
    }
    System.out.println("Exit");
    System.exit(0); //stop runtime
} //run()

/*
* @return String
*/ 
@Override 
public String toString(){
    return this.pq.toString();
} //toString()

private void serveCustomer(){
    long elapsedTime = System.nanoTime()-startTime;
    while((elapsedTime)<(serviceCustomerAt)){ 
        elapsedTime += System.nanoTime()/10000000;
    }
    if(pq.size()!=0){
        System.out.println("Dequeued customer @[" + dateFormat.format(new Date())
                + "]");
        pq.poll(); //remove first element of queue
    } else {
        System.out.println("ERROR: Queue is empty!");
    }
} //serveCustomer()

/*
* @param String ID
*/ 
private void newCustomer(int ID){
    long elapsedTime = System.nanoTime()-startTime;
    long waitTime = (long)generateWaitTime()*1000000;
    long generateAt = elapsedTime+waitTime;

    while((elapsedTime)<(generateAt)){/*Wait*/    
        elapsedTime += System.nanoTime()/10000000; //increment elapsed time
    }      
    serviceCustomerAt = 0; //reset service wait time value
    System.out.println("Customer # " + totalCustomers + " added to queue. . .");
    totalCustomers++;
    pq.offer(ID); //insert element into PriorityQueue
    System.out.println("Queue size: " + pq.size()); //output linesize
    assignTimestamp(ID); //call assignArrivalTime() method

    //Calculate time until customer served
    waitTime = (long)generateWaitTime()*1000000;
    elapsedTime = System.nanoTime()-startTime;

    serviceCustomerAt = elapsedTime + waitTime;
    System.out.println("Service delay: " + waitTime/1000000);
} //newCustomer()

/*
* @param String ID 
*/
private void assignTimestamp(int ID){
    timeStamp.add(ID + ": " + dateFormat.format(new Date()));
    System.out.println(timeStamp.get(totalCustomers-1));
} //assignArrivalTime()

* @return int 
*/
private int generateWaitTime(){
    //Local variables
    int Low = 1000;  //1000ms
    int High = 4000; //4000ms
    return rand.nextInt(High-Low) + Low;
}//generateWaitTime()

/*
* @return String
*/
private static String insertDivider(){
    return ("****");
}//insertDivider()

output:

run:
Instantiated new GroceryStoreSimulation @ [2012/03/13 - 01:55:23 AM]

---

Delay until first customer: 1263
Customer # 0 added to queue. . .
Queue size: 1
0: 2012/03/13 - 01:55:24 AM
Service delay: 1373
Dequeued customer @[2012/03/13 - 01:55:24 AM]
Customer # 1 added to queue. . .
Queue size: 1
1: 2012/03/13 - 01:55:24 AM
Service delay: 2188
Dequeued customer @[2012/03/13 - 01:55:24 AM]
Customer # 2 added to queue. .
.
.
.
Service delay: 3379
Dequeued customer @[2012/03/13 - 01:55:24 AM]
Customer # 927 added to queue. . .
Queue size: 1
927: 2012/03/13 - 01:55:24 AM
Service delay: 2300
Service delay: 2300BUILD STOPPED (total time: 1 second)

Answer 1

Try changing

   while((elapsedTime)<(generateAt)){/*Wait*/    
       elapsedTime += System.nanoTime()/10000000; //increment elapsed time
   }

to

   while((elapsedTime)<(generateAt)){/*Wait*/    
       elapsedTime = System.nanoTime()-startTime; //update elapsed time
   }   

NOTE: I believe you should re-work your two methods to not do any waiting, but rather simply check if it is time to queue/de-queue a customer. In the main while loop, you can add a Thread.sleep(1000) so that every 1 second, you call each method which checks if it's time to queue/de-queue a customer. Upon successfully doing so, update the time at which the next person should be serviced/generated.

Answer 2

A couple things to think about:

You're simulating a 12-hour day, at 1 minute resolution, there is no need to have your program actually running for any specific amount of time (ie there is no need for Thread.sleep() at any point).

You do want a FIFO queue, a PriorityQueue is, by definition, not a FIFO queue. (I haven't checked if it actually makes a difference in your case, but you should probably be aware of the difference).

Doing things like this:

try {
  newCustomer(totalCustomers); //enque customer
  serveCustomer();
} catch(Exception e){/*Catch 'em all*/}

Will cause nothing but frustration and hair pulling.

Edit

Unless there's a specific requirement to use sleep() to time your code (wasn't clear, but I'm assuming there isn't), something like this would be a lot easier:

for(int minute = 0; minute < 720; minute++){
  // process customer arrival and service
}

Hopefully that can give you some ideas.