40 Points

The following BASIC code simulates the single-server queue with FIFO service. It generates the interarrival
times and the service times for 100,000 customers; and it produces estimates of the server utilization, the
fraction of customers who must wait in the queue, and the average waiting time.

100
110
120
130
140
150
160
170
180
190
200

FOR i = 1 TO 100000
IA =
(generate interarrival time)
T = T + IA
W = W + X IA
IF W < 0 THEN W = 0
IF W > 0 THEN c = c + 1
SW = SW + W
X =
(generate service time)
SX = SX + X
NEXT i
PRINT SX/T, c/100000, SW/100000

Adapt the program and run it (using the language of your choice) for four different service-time
distributions:
(1) exponential service times, with mean service time E(X) = 0.5
(2) constant service time, X = 0.5
(3) X ~ U(0,1)
(4) P(X=1/3) = 0.9, P(X=2)= 0.1
Assume that the interarrival times are exponentially distributed with mean value 0.625 (that is, Poisson
arrivals with rate = 1.6) . Fill in the table. For case (1), draw the graph of the theoretical distribution
function of waiting times, Fw(t); and, on the same axes plot the simulation estimates at the values of t as t
goes from 1 to 12 in increments of 1, and fill in the corresponding table.
Theory for the M/G/1 queue: If is the arrival rate and X is the service time, then the server utilization is
given by
= E(X) if E ( X ) < 1
1
if E ( X ) 1

The probability that a customer must wait in the queue is
P(W > 0 ) = ,
and the mean waiting time is given by the famous Pollaczek-Khintchine formula,
E (W ) =

E( X )
V (X )

1 + 2
E (X ) .

1
2

In addition, if the service times are exponentially distributed, and the service is FIFO, then

0

t
Fw(t) =
( 1 )
E(X)
1 e

(t < 0 )
(t 0 )

There is no simple formula for Fw(t) when the service times are not exponentially distributed. (Therefore,
simulation is an important tool for the analysis of queues whose service times have any arbitrary specified
distribution of service times; and the theoretical results for the special case of exponential service times are
important because they can be used to check the logic and accuracy of the simulation.)

X

theory

simulation

P(W > 0)
theory
simulation

P(W > 0.5)
theory
simulation

1
2

NA

3

NA

4

NA

Fw(t)
t
-1
0
1
2
3
4
5
6
7
8
9
10
11
12

theory

simulation

theory

E(W)
simulation