Supermarket Simulation (Checkout Line Simulation)

Question!

 

Write a program that simulates a (single) checkout line at a supermarket. The line is a queue object. Customer(i.e., customer objects) arrive in random integer intervals of 1—4 minutes. Also, each customer is served in random integer intervals of 1—4 minutes. Run the supermarket simulation for a 12-hour day (720 minutes) using the following algorithm:

 

 

 

For the better service at the next time, the supermarket decided to record the name of the customers. A customer’s name is a random integer between 0 to 10000. Whenever a new customer arrives at the queue, you assign a new random name to the customer. We assume the customer’s name is unique for every customer. For efficiency, the customers’ names are recorded in the binary search tree structure (forget about balancing).

 

 

After the simulation, you display the binary tree for the customers’ names on the screen. The function should output the tree row by row, with the top of the tree at the left on the screen and the bottom of the tree toward the right of the screen. Each row is output vertically. For example, one example output is as follows:

 

 

 

 

 

 

where 83 is a root of the tree having left child 71 and right child 97, and so on.

 

 

 

 

Solution!

 

1) Description the usage of the program.

 

 

1-1) Execution

 

* At the Console Window, Use a similar form following. And there are two execution way.

 

① First Way : If you just input the command ‘simulate’, You can simulate the program with default value.

- Default Value 1: Maximum Interval time of customers’ arrival is 4 (1 ~ 4 minutes)

   - Default Value 2: Maximum Interval time of service for customer is 4 (1 ~ 4 minutes)

 

   - Default Value 3: Simulation Time : 720 minutes

 

 

 

 

 

 

② Second Way : You can add the extra parameters like the following example

  - First extra parameter: You can set the maximum interval time of customers’ arrival

  - Second extra parameter: You can set the maximum interval time of service for customer

 

  - Third extra parameter: You can set the simulation time

 

 

 

* Notice : If you just only input one or two additional parameters, the parameters are not applied to program. So this program is executed with default values

 

 

 

 

1-2) Execution Result

 

* You can see the following result after execution

 

 

 

 

It shows the number of customers in the line at every time, (This data amount is so large, So you can’t see the all data)

And the ‘in’ and ‘out’ marks mean that customers in and out at the checkout line.

 

 

 

 

 

 

It shows the maximum number of customers in the queue at particular time and longest wait time of particular customer among all customers.

 

 

 

 

 

 

It shows the binary search tree of customers’ names to 5 levels of the name tree from the root.

 

 

 

 * Another Example (Execution command : simulate 4 4 720)

 

 

 

 

2) Implementation

 

 

2-1) Queue

 

 

l  I implemented the Queue structure using double linked list.

The queue in this program consist of queue node structure, some additional variables and some functions(Enqueue, Dequeue and so on).

 

 

 

Implemented Part	Location	Description
Queue Node Structure	20 ~ 25 Line	It is used to save one node in queue
Head and Tail Node	36 Line	It is the head and tail node for double linked list, that is to say, head node means ‘front’ and tail node means ‘rear’ in queue concept.
Variables for queue	37 ~ 40 Line	It is used to solve the problem about queue in spec.
Functions for queue	48 ~ 52 Line	There is functions’ declaration for queue operation
InitQueue()	151~161 Line	Initialize the queue
Enqueue(int value)	164~183 Line	Put data to rear of queue
Dequeue()	186~205 Line	Get data from front of queue
ClearQueue()	208~233 Line	Release all queue data. Namely, Initialize the queue
AddWaitTimeToQueue()	226~236 Line	Add the waiting time at the line per customer (Extra function)

 

 

 

2-2) Binary Search Tree

 

l  The tree in this program consist of tree node structure, some additional variables and some functions(InsertToTree, OutputTree and so on)

 

 

Implemented Part	Location	Description
Tree Node Structure	28 ~ 33 Line	It is used to save one node in tree
Base Node	43 Line	It is the base node of tree
Variables for queue	44 ~ 45 Line	It is used to solve the problem about binary search tree in spec.
Functions for queue	55 ~ 58 Line	There is functions’ declaration for tree operation
InitTree(int initValue)	242~248 Line	Initialize binary search tree
InsertToTree(int value)	251~280 Line	Insert data to proper position of tree
GetNewCustomerNumber()	283~300 Line	Get new customer's name without overlapping (Extra function)
OutputTree(tnode *node, int totalSpace, int depth)	307~326 Line	Output the tree on screen

 

 

 

 

3)Test Cases

 

3-1) What is the maximum number of customers in the queue at any time?

 

* To solve this problem, I makes two additional variables – maxNumber, maxTime

  > maxNumber : this variable always maintain the maximum number of customers in queue

  > maxTime : maxTime save that time when maxNumber variable is updated

* And every time when 1 minute passes, I checked the number of customers in queue. So if the number of customers in current-state queue is larger than maxNumber, change the maxNumber data as number of customers in current-state queue. So the maxNumber always can maintain the maximum number of customers in the queue at particular time

* Please, refer the 101~105 Lines in source code.

 

 

 

 

3-2) What is the longest wait any one customer experiences?

 

* To solve this problem, I save the customer’s waiting time in the each queue node (waitTime) and maxWaitTime.

> maxWaitTime: this variable always maintain the longest wait time of particular customer among all customers.

First, customer comes to the checkout line, Input the customer data to queue, and initialize the customers’ wait time to 0. And Whenever 1 minute passes, add 1 minute to the each customers’ wait time. And if a customer get out from the checkout line (Dequeue operation), Compare the value with maxWaitTime. So if the current customer’s wait time is larger than maxWaitTime, change the maxWaitTime data as the current customer’s wait time.

* Please, refer the 122~128 Lines in source code.

 

 

 

 

3-3) What happens if the arrival interval is changed from 1—4 minutes to 1—3 minutes?

 * These are some examples that the arrival interval is changed to 1-3 minutes

 

 

 

 

* As you can see, If the arrival interval is changed from 1 – 4 minutes to 1 – 3 minutes, Generally, the maximum number of customers and longest wait time is getting lager than data of general case.

 

* The reason: ‘The arrival interval time is getting smaller’ means ‘the many more customers can come to the checkout line’. Because the arrival interval time is small, the queue maybe take more customers. But the service interval time is not decreased. So the same service time is needed as ever.

 

 

 * Result : The number of customers that comes in checkout line is increased and the processing time of service for customers is same. In result the queue is larger and the processing efficiency will be slower.

 

 

 

 

Source & Execution Files Download

 

supermarket_simulation.zip