The project described below belongs to an important class of computational problems known as Discrete Event Simulation. Discrete Event Simulation (DES for short) is an important to determine the resource requirements in a system that is rapidly changing with time. For example, the system could be travelers using an interstate highway and the resource may represent the number of lanes, or the number of toll booths, or the number of tellers in a bank. The goal of simulation is to try different choice for system parameters (e.g. the number of toll booths) and calculate the cost (here cost may be the waiting time to pass the toll booth). By experimenting with different parameters, we can compare different solution and reach one that is acceptable for all the parties concerned.
Consider a service station (such as a checkout counter in a super-market or a bank) in which customers arrive at various times. The times are represented in seconds starting from a fixed time. For example, if the staring time is fixed at 8 AM on a fixed day, the arrival at 8:04:13 will correspond to the integer 253. Each customer requires the service of only one server and all the servers provide the same service. This is typically the case, for example, in a super-market or bank. There are k-servers available for some fixed k. (k is part of the input to your program. For each customer, you are given the time it takes to provide service. (Note that this number can be different for different customer – for example, in the case of super- market, the time taken to complete the check-out depends on the number of items you bought and on other factors such as whether you are paying with cash, debit or credit card etc.) When a customer arrives, he/she joins a single queue. When a server j completes providing service, the person in the front of the queue is taken in for service by j. The problem you are to solve is the following: what is the waiting time for each customer under the servicing scheme described above? In addition, you are also required to output the ID number of the server who serviced customer j, for all j.
The data structure you would need to solve this problem efficiently is a queue to hold the customers and a heap to hold information about the servers. DES proceeds by moving the system through various times. However, we will not go through every second and see how the system changes. The reason is that significant changes only happen at discrete moments and the simulation focuses only on such moments – for example, when a new customer arrives, or when a server finishes serving one customer so he/she is ready to take the next one. Suppose currently the time is t. The heap will contain, for each server k, a key that indicates when k will complete servicing the current customer.
The details of the simulation are as follows:
Additional data structure: A heap of size k to hold information about when each server will be ready to take the next customer after the current time which is stored in variable ctime. In addition, the heap will also contain the ID number of the server. Thus the heap’s data member array (as named in the text) will have two fields – time and id.
The complete algorithm is described below: See image.
Example: Suppose the arrival times and service times of 10 customers are:
arrive : 0 4 6 9 14 20 24 31 39 40
stime: 26 18 16 11 27 19 24 14 20 16
Let the number of servers k = 4.
Then it can be checked that the waiting times and server ID’s for the customers (if we use the above algorithm) are:
wait = 0 0 0 0 6 2 0 0 2 5
serveID = 1 2 3 4 4 3 2 1 3 1
When the program is run, it should ask the user for arrive vector, then ask for stime vector. In each case, the user enters the arrays in a single line followed by ENTER. Finally, it asks for the value of k. The console output shall display the wait and serveID vectors.