Department of Computer Science and Statistics, Lumière University Lyon 2

L3 IDS – Year 2012-2013

Project C: Queue Simulation
Marian-Andrei Rizoiu[Link]

We wish to simulate using a C program the behavior and measure the performance of a
queueing system (like supermarket checkouts or toll booths). We will name the entities that
transient in this system the clients. The goal is to optimize or size the studied system.

Customers arrive at the entrance of the system on an arrival date. They are assigned to the longest queue.
small size. Each client is treated in units of time (system parameter). Between the end of
processing of one client and the beginning of processing the next client, there is a delay in time units.
The simulation will be managed using a schedule, which is a list of events to be processed.
each at a given date (or time). Events can be of three types: arrival of a customer,
start of processing a client and end of processing a client (detailed below). All clients
go through three stages: they arrive and they are assigned to the shortest girl (an event
arrival of a client is inserted into the schedule), its processing begins (an event start of
treatment of a client is inserted into the schedule) and after the processing time it is all ready
event end of processing of a client is inserted into the schedule).

Based on a list of customer arrivals, you will need to generate the schedule and display it at the end.
the execution, as well as the following performance measures:
Maximum queue size
Average queue length
Average response time (average processing time for clients). The response time for a
The client is the difference between his arrival and the end of processing.
Average flow (average number of customers per unit of time)

Data structures modeling queues

Record including the following fields

Date of arrival in the system
Pointer to the next client in a queue

Queue list:
Let it beNthe number of queues, which is a parameter of the program.

Size tableNintegers representing the size of the queues

Size tableNof pointers to the head of the queues (linked lists)
Size tableN from pointers to the queue tails

Client Client Client

Size Head Follow-up Dtarr Follow Dtarr Suiv Queue

0 3 0 0 4 ... 11 0

1 T1 1 Queue file n° 0 1
NULL

2 T2 2 2

... ... ...

N-1 T(N-1) N-1 N-1

1/4
Simulation management - events
Soit the current date.
1. Arrival of a new client (event type A)
Create a new client and add them to the shortest queue. If there are 2 queues with the
same size (the smallest), add it to the girl with the smallest order number.
Add an event "Arrival of a new client" to the schedule on the dated and the girl
assigned.
If the queue was empty before the arrival of the new client, he is served immediately: add in
the schedule an event start of processing a client on the date.

2. Start of client processing (event type D)

Add an event 'Start of client processing' to the schedule on the dated and the girl
assigned.
Think about generating an event "End of client processing" on the date d+tt-1.
d+tt-1 (inclusive) are time units.

3. End of processing a client (event of type T)

Remove the client from their queue.
If the queue is not empty, the processing of the next customer (an event 'Start of
The processing of a client starts on date+d+ta+1. The waiting list is in a resting period.
dependent time units.

Data structure for managing the simulation

Registration including the following fields

A, D or T
Execution date
Concerned queue
Pointer to the next event in the schedule

Schedule: Linked list of events sorted in ascending order of execution date. The linked list
events must be sorted by:
1. ascending order of execution date
2. for equal dates, in ascending order of the event code (A < D < T)
3. for equal dates and equal codes, by order number of the queue.

Event Event Event

Type Date Follow-up File Type Date Follow-up File Type Date Follow-up File

Head A 0 0 T 5 0 ... T 10 1 NULL

Schedule

Inputs and outputs

All parameters are read from a text file in the following format: the first line contains N (the
number of girls), tt (processing time) and ta (waiting time between clients), separated by a space
(blank). The following lines contain the arrival dates of the clients, one per line. The number of clients
is variable, you will need to read until the end of the file. The input file is called '[Link]' and is located
in the same folder as the executable of your project.
2/4
I don't know
client arrival date 0
client_arrival_date_1
client_arrival_date_2
client arrival date 3
client_arrival_date_4
...
...
The output of your software is a text file '[Link]' (you will need to create it in the same folder)
that the executable). The file contains (i) on the first line the performance measures (size
maximum queue length
separated by spaces and with a precision of 2 decimals (rounded to the nearest number, display
with the format "%.2f") and (ii) on the following lines the schedule, with one event per line. A
the event is described by its type, date and girl separated by a space (blank).
max_size
type1
type1 date1 girl1
type1 date1 fille1
...
...

Execution example - inputs and outputs

No text provided for translation.
2 5 1
0
0
1

The provided text is not available for translation.

2.00 1.82 6.67 0.27
A 0 0
A 0 1
D 0 0
D 0 1
A 1 0
T 4 0
T 4 1
D 6 0
T 10 0

Details of measurement calculation:

File Temps 0 1 2 3 4 5 6 7 8 9 10
0 1 1.3 1.3 1.3 1.3 3 3 3 3 3 3 Rest period
1 2 2 2 2 2 Treatment finished
Girl's size: 2 3 3 3 3 1 1 1 1 1 1 1.82

Above is the table with the 2 girls waiting. The 3 clients are marked with the numbers 1, 2, and 3.
Format 1 represents the client waiting, before the start of the processing, format 1 represents the client in
train to be treated.
Maximum queue size: 2 for the girl 0 between moments 1 and 4:
1.82
You must be treated at every moment. WARNING: there are 11 moments in time (from 0 to 10);
Average response time (average processing time for customers). 20 / 3 = 6.67 if we count the
nombre d'apparitions pour chaque client :client 1 : 5 fois,client 2 : 5 fois,client 3: 10 fois.
Average flow (average number of customers per unit of time) 0.27 = 3 customers in 11 units of time.

3/4
Notes, deadline and information.
Project submission: 06/05/2013 at 8 AM.
The report and the software must be sent electronically by the email of the person in charge.
Course. The email must have the subject tag [ProjectC] followed by the student’s first and last name.
[ProjectC] RIZOIU Marian-Andrei. Don’t forget to get yourself
yourself in copy of the email, in order to be able to prove (if necessary) that the email was transmitted in the
deadlines.
Attention: each day of delay incurs a penalty of 1 point on the final grade. Delays are
calculated by whole day. Example of delay calculation: an email sent on May 6 at 10 am (2 hours of
delay) already incurs a penalty of one point.
All correspondence will be sent to the following email address:[Link]@[Link].
Attention: please strictly follow the input and output format. If your software does not comply with the
formats, the score of the automatic evaluation (see below) will be 0 (zero).
You will need to provide a makefile to compile your software. In the automatic evaluation, your
The software will be compiled with the command 'make' and executed with 'make run'. The absence of makefile
(or compilation or execution error) results in a score of zero in the automatic assessment.

Notation :
10 points automatic evaluation. 10 test cases (input files) will be provided to your software.
and your output will be compared with the correct output. If both are identical, you will be awarded one point.
agreed. Otherwise, zero.
10 points for manual code evaluation. The code must be properly presented (indentation).
clear (use of a specific standard for names) and commented (by reading the comments, one must)
to be able to understand the program). All of these files must be provided in the form of a
archive (.zip or .[Link]).

4/4