Question

Queues are often used to represent lists of things that are being processed according to the order in which they arrived -- i.e. "first come, first served".  

Assignment

Write a program that simulates the minute-by-minute operation of a checkout line, such as one you might find in a retail store. Use the following parameters:

1) Customers arrive at the checkout line and stand in line until the cashier is free.

2) When they reach the front of the line, they occupy the cashier for some period of time (referred to as ServiceTime) measured in minutes.

3) After the cashier is free, the next customer is served immediately.

4) Customers arrive at the checkout line at ArrivalRate per minute. Use the function included below (randomChance()) to return the number of customers arriving in a given minute, determined randomly.

5) The line can only hold so many people, MaxLineSize, until new arriving customers get frustrated and leave the store without purchasing anything.

6) ServiceTime is determined at the point the customer reaches the cashier, and should be taken from the random interval MinServiceTime and MaxServiceTime -- use the function randomInt() provided.

7) The overall time of the simulation is SimulationTime, measured in minutes.

The program should take 6 inputs (to be read from a text file named simulation.txt, as numbers only, one per line, in this order):

- SimulationTime - total number of minutes to run the simulation (whole number).

- ArrivalRate - per-minute arrival rate of customers (a floating point number greater than 0 and less than 1). This number is the "percent chance" that a customer will arrive in a given minute. For example, if it is 0.4, there is a 40% chance a customer will arrive in that minute.

- MinServiceTime - the minimum expected service time, in minutes (whole number).

- MaxServiceTime - the maximum expected service time, in minutes (whole number).

- MaxLineSize - the maximum size of the line. If a new customer arrives and the line has this many customers waiting, the new customer leaves the store unserviced.

- IrateCustomerThreshold - nobody enjoys standing in line, right? This represents the number of minutes after which a customer becomes angry waiting in line (a whole number, at least 1). These customers do not leave, they only need to be counted.

At the end of each simulation, the program should output:

- The total number of customers serviced

- The total number of customers who found the line too long and left the store.

- The average time per customer spent in line

- The average number of customers in line

- The number of irate customers (those that had to wait at least IrateCustomerThreshold minutes)

You are free to use any STL templates as needed (queue or vector, for example).

An example input file is posted in this week's Module here.

Example Run

The output should look similar to this:

Simulation Results
------------------
Overall simulation time:     2000
Arrival rate:                 0.1
Minimum service time:           5
Maximum service time:          15
Maximum line size:              5

Customers serviced:           183
Customers leaving:             25
Average time spent in line: 33.86
Average line length:         3.15
Irate customers                10

What to Submit

Submit your .cpp file (source code for your solution) in Canvas.

Random Functions

Use these provided functions for generating your random chance (for a customer arrival) and interval for service times.

bool randomChance(double prob) { 
    double rv = rand() / (double(RAND_MAX) + 1); 
    return (rv < prob); 
} 

int randomInt(int min, int max) { 
    return (rand() % (max - min) + min); 
} 

Before calling these functions be sure to seed the random number generator (you can do this in main()):

srand(time(0));

Outline:

#include <iostream>
#include <queue>

using namespace std;

int main()
{
queue<int> myQ;

// For each test case, do a loop like this:
for (int i = 0; i < SIMULATION_TIME; i++) {
if (randomChance(ARRIVAL_RATE)) {

// Did a customer arrive in this minute?
// If so, put them on the queue
// - Is the queue full? If so, they left.
// If not, continue with rest of the loop

// Checking on the checkout line:
// - Is the current person done?
// - If so, take the next person
// - Get
// - Record how long they waited
// - Generate a random for how long
// they will take at the checkout

// Record various metrics:
// - Average wait time
// - Is the customer irate?
// - Average queue length
// - Increment number of customers serviced
// - How many left because the line was full?

}

// Print a report here

return 0;
}

Test input:

2000
0.10
5
15
5
20
10000
0.05
5
15
5
18
2000
0.20
5
20
10
10
2000
0.20
1
5
10
25
20000
0.50
1
2
50
10

Answer 1

The input file contains input for multiple simulations, therefore, input is read till the end of file. Rest explanation is in the code comments. Read file using fstream library.

Please note that input is read from simulation.txt. Also, as random numbers are involved, the output would be different for every code run.

Program:

#include <iostream>
#include <queue>
#include <stdlib.h>   // to use random
#include <time.h>   // for random seed
#include <fstream>   // read file

using namespace std;

bool randomChance(double prob) {
double rv = rand() / (double(RAND_MAX) + 1);
return (rv < prob);
}

int randomInt(int min, int max) {
return (rand() % (max - min) + min);
}

int main()
{
   // input file
   ifstream fin;
   fin.open("simulation.txt");

   // get results for all test cases
int testCaseCount = 0;
while(!fin.eof()) {
  
testCaseCount ++;
  
   // queue of customers arriving
   queue<int> myQ;
  
   // inputs
   int SimulationTime, MinServiceTime, MaxServiceTime, MaxLineSize, IrateCustomerThreshold;
   double ArrivalRate;
  
   // variables required for simulation.
   int currentPerson = 0, startTime, waitTime;
   bool isPersonServed = false;
  
   // output variables
   int customersServiced = 0, customersLeft = 0, irateCustomers = 0;
   double avgWaitTime = 0.0, avgLineLength = 0.0;
  
   // take input
   fin>>SimulationTime;
   fin>>ArrivalRate;
   fin>>MinServiceTime;
   fin>>MaxServiceTime;
   fin>>MaxLineSize;
   fin>>IrateCustomerThreshold;
  
   srand(time(0));
  
   // For each test case, do a loop like this:
   for (int i = 0; i < SimulationTime; i++) {
       // Did a customer arrive in this minute?
       // If so, put them on the queue
       // - Is the queue full? If so, they left.
       // If not, continue with rest of the loop
       if (randomChance(ArrivalRate)) {
          
           if(myQ.size() == MaxLineSize) {
               customersLeft ++;
           }
           else {
               // store at which minute customer arrives
               myQ.push(i);
           }
       }
      
       // Checking on the checkout line:
       // - Is the current person done?
       // at least one person should be there
       if(currentPerson == 0 && myQ.size()>=1) {
          
           if(isPersonServed) {
           // remove the current customer
           myQ.pop();
          
           // Increment number of customers serviced
           customersServiced++;
          
           // - Record how long they waited
           // and add it to avg wait time
           waitTime = i - startTime;
           avgWaitTime += waitTime;
          
           // irate customer count
           if(waitTime>=IrateCustomerThreshold)
               irateCustomers++;
           }
      
           // queue is not empty
           if (!myQ.empty()) {
              
               // - If so, take the next person
               startTime = myQ.front();
              
               // - Generate a random for how long
               // they will take at the checkout
               currentPerson = randomInt(MinServiceTime, MaxServiceTime);
               isPersonServed = true;
              
           } else {
           // no person to serve
           isPersonServed = false;
           }
       } else if(currentPerson>0) {
           currentPerson --;   // time left to serve the current person
       }
      
       // Average queue length
       avgLineLength += myQ.size();
   }
  
   avgWaitTime = 1.0 * avgWaitTime / customersServiced;
   avgLineLength = 1.0 * avgLineLength / SimulationTime;
  
   // report
   cout<<"Simulation Results for test case #"<<testCaseCount<<endl;
cout<<"------------------"<<endl;
cout<<"Overall simulation time:\t"<<SimulationTime<<endl;
cout<<"Arrival rate:\t"<<ArrivalRate<<endl;
cout<<"Minimum service time:\t"<<MinServiceTime<<endl;
cout<<"Maximum service time:\t"<<MaxServiceTime<<endl;
cout<<"Maximum line size:\t"<<MaxLineSize<<endl;
cout<<endl;
   cout<<"Customers serviced:\t\t"<< customersServiced<<endl;
   cout<<"Customers leaving:\t\t"<<customersLeft<<endl;
cout<<"Average time spent in line:\t"<<avgWaitTime<<endl;
cout<<"Average line length:\t\t"<<avgLineLength<<endl;
   cout<<"Irate customers:\t\t"<<irateCustomers<<endl;
cout<<"------------------"<<endl<<endl;
  
}
  
// close input file
fin.close();

return 0;
}

Sample Output:

Code screenshot: