TITLE QUEUEING SIMULATION INTRODUCTION A queue is a sequence of elements, all of
ID: 3735934 • Letter: T
Question
TITLE
QUEUEING SIMULATION
INTRODUCTION
A queue is a sequence of elements, all of the same type, to which elements can be appended at one end (the rear of the queue) and from which elements can be removed at the other end (the front). Queues are first-in-first-out (FIFO) structures that mimic the behavior of such systems as people in lines, cars at traffic lights, and files to be printed.
A queueing system consists of one or more queues of elements waiting to be served by one or more servers. When an element is removed from the front of a queue, a server serves that element. How queues and servers interact and parameters such as the numbers of queues and servers, how often new elements arrive, and how often servers remove elements from queues determine the behavior of a queueing system.
A queueing simulation is a program that simulates a queueing system. A probabilistic simulation calls a pseudo-random number generator to determine if events occur, and their parameters, at each tick of the simulation's clock.
DESCRIPTION
Design, implement, test, and document a probabilistic simulation of a queueing system with several queues and several servers, one server for each queue, as in a grocery or discount store. Because there are several lines, each arriving customer always joins the line that is currently the shortest. If several lines are equally short, the new arrival may join any one of them. A line with a free teller is "shorter" than one whose teller is occupied. Once in a line, a customer does not leave it until served.
The program reads from the terminal the parameters of the simulation---how many queue/server pairs, the longest time for a transaction, the probability that a customer arrives during a single tick, the duration of the simulation---and a seed value for the random number generator. It simulates the queueing system for the specified duration, showing a picture of the system at every clock tick, then reports some statistics: the average time each customer waited, the longest time any customer waited, the number of customers served, and the numbers of customers left in queues.
The number of queue/server pairs, of course, is at least 1. The probability that a customer arrives during one tick is a percentage, thus an integer between 0 and 100. Each transaction's time is random, uniformly distributed between one tick and a positive maximum value entered from the terminal.
INPUT
From the terminal the program reads:
the number of queue/server pairs (lines and their tellers),
the probability that a customer will arrive in a single tick (a percentage, thus an integer between 1 and 100);
the longest time a transaction may take, a positive integer;
the duration of the simulation in ticks, at least 1; and
an integer seed value for the pseudo-random number generator.
OUTPUT
The program's output, directed to the terminal, is a snapshot of the system at each clock tick during the simulation, followed by these statistics:
the number of customers served,
the average time (number of ticks) the customers who were served waited,
the longest time any one customer waited, and
the number of customers left in queues when the simulation terminated.
ERRORS
The program may assume that the input values are as described above; it need not detect any errors.
EXAMPLE
Below is an abbreviated script of a run of such a program. Each block of output lists the clock value, the times remaining in each teller's current transaction, and the arrival times of the customers waiting in the lines. For the first few ticks, each arriving customer is served immediately; these customers join queues but are dequeued without waiting.
Even with the same input values, your program will almost certainly produce different results, since a psuedo-random number generator's values can generally be used in several ways to get the effects we desire. Examples like this one are intended to show what the program's output might look like, NOT to provide a standard to determine the correctness of your code. Your tests and examples must be different.
OTHER REQUIREMENTS
Implement the Queue abstract data type in a class, using the sequential (array-based) implementation described in class.
HINTS
Declare the array of queues and the array of teller times after the program has read in the number of line/teller pairs, so that the program has exactly the specified number of each and there is no upper limit on the number of lines. Initially, the array of teller times is all zeros. When a teller is free---that is, when a value in this array is zero---and its queue is not empty, then a customer is dequeued from that queue and served.
Consider a function that returns the index of the "shortest" line; it will examine both the lengths of the queues and the remaining transaction times. Consider also a function that returns the total length of all the queues.
Explanation / Answer
//Queue.cpp
#include <iostream>
#include <cstdlib>
#include "implement.cpp"
#include "header.h"
using namespace std;
int main()
{
//Variable Decleration
int DURATION;
int ARV_PROB;
int Max_TakenTime;
int trans_time; //to hold the maximum transiction time
int people; //to hold no. of people
int entry_time; //to hold the entry_time for each person
int wait_sum = 0;
int wait_time; //to hold the time a person waits in the queue.
int queuecount; //to hold number of servers
int shortest_line;
int total_people = 0;
int seed; //to hold the previous rand number
cout << "Enter these parameters of the simulation:" << endl;
cout << " The number of queue/server pairs: ";
cin >> queuecount;
cout << " The probability that a customer arrives in one tick (%): ";
cin >> ARV_PROB;
cout << " The maximum duration of a transaction in ticks: ";
cin >> Max_TakenTime;
cout << " The duration of the simulation in ticks: ";
cin >> DURATION;
cout << "Enter a random number seed: ";
cin >> seed;
srand(seed);
cout<<" n ";
Store_Queue Line[queuecount]; //queue for each line
int trans_time_arr[queuecount];
//initializing the time array to hold transisition time for each line.
for(int index = 0; index < queuecount; ++index)
trans_time_arr[index] = 0;
for(int time = 0; time < DURATION; ++time)
{
if(rand() % 100 < ARV_PROB)
{
shortest_line = Shortest_queue(Line, queuecount); //checking for the shortest queue to add new customer
Line[shortest_line].enqueue(time);
}
for(int Line_number = 1; Line_number <= queuecount; ++Line_number)
{
if(trans_time_arr[Line_number] == 0) //if the store receptionist is free
{
if(!Line[shortest_line].empty())
{
entry_time = Line[shortest_line].dequeue();
wait_sum += time - entry_time;
wait_time = time - entry_time;
++people;
trans_time_arr[Line_number] = rand() % Max_TakenTime + 1;
}
}
else
--trans_time_arr[Line_number];
}
//SnapShot of the current figure
cout<<time <<" ";
for (int index=0;index < queuecount; ++index)
{
cout<<" "<<trans_time_arr[index]<<" "<< Line[index]<<" ";
}
}
//total number of people left in the array of queues
for(int i = 0; i < queuecount; ++i)
{
total_people += Line[i].length();
}
//output of the end figure
cout << people << " customers waited an average of "<<wait_sum/people<<" ticks."<<endl;
cout << "The longest time one customer waited was " << wait_time << " ticks." << endl;
cout << total_people << " customers remain in the lines." << endl;
return 0;
}
------------------------------------------
//implement.cpp
#include <iostream>
#include "header.h"
using namespace std;
void Store_Queue::enqueue(int Time)
{
Node* temp;
temp = new Node;
temp -> data = Time;
temp -> next = NULL;
if(first == NULL)
first = temp;
if(rear == NULL)
rear = temp;
++count;
}
Store_Queue::Item Store_Queue::dequeue()
{
Item popped;
Node* temp;
temp = new Node;
popped = first -> data;
temp = first;
first = first -> next;
--count;
delete temp;
if(first == NULL)
rear = NULL;
return popped;
}
int Store_Queue::Shortest_queue(Store_Queue q[], int queuecount)
{
int short_line = 0;
for(int i = 0; i < queuecount; ++i)
{
if(q[i].length() < q[short_line].length())
{
short_line = i;
}
}
return short_line;
}
ostream& operator << (ostream& out_s, Store_Queue Line)
{
Store_Queue::Node* cursor;
Store_Queue::Item print;
for ( cursor = Line.first; cursor != NULL && cursor -> next != NULL ; cursor = cursor -> next)
{
print = Line.dequeue();
out_s<< print <<" ";
Line.enqueue(print);
}
if(cursor != NULL)
{ print = Line.dequeue();
out_s << print << " ";
Line.enqueue(print);
}
return out_s;
}
-------------------------------------------
//header.h
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
#include <cstdlib>
using namespace std;
int typedef Item;
struct Node
{
Item data;
Node* next;
};
Node* first;
Node* rear;
Item count;
class Store_Queue
{
int typedef Item;
public:
//member functions
Store_Queue(){first = NULL;
rear = NULL;
count = 0;};
~Store_Queue(){first = NULL;
rear = NULL;
count = 0;};
//public member functions
void enqueue(Item Time);
Item dequeue();
bool empty(){return first == NULL;};
size_t length(){return count;}
int Shortest_queue(Store_Queue q[], int queuecount);
//friend function
friend std::ostream& operator << ( std::ostream& out_s, Store_Queue Line);
private:
struct Node
{
Item data;
Node* next;
};
Node* first;
Node* rear;
Item count;
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.