The M/G/1 queue has exponentially distributed interarrival
times and an arbitrary distribution for service times. The
increase in generality compared to the M/M/1 queue comes with
a price: the M/G/1 queue does not have a general, closed form
distribution for the number of jobs in the queue in steady
state. It does, however, admit a general solution for the
average number of jobs in the queue, and
application of Little's Theorem provides the corresponding
result for the average time spent in the queue. Collectively,
these results are known as the Pollaczek-Khinchin
mean value formulae.
The following derivation of the Pollaczek-Khinchin mean value
formulae for the M/G/1 queue assumes FCFS scheduling, to
simplify the analysis. However, the formulae are valid for
any scheduling discipline in which
-
the server is busy if the queue is non-empty,
-
no job departs the queue before completing service, and
-
the order of service is not dependent on knowledge about
job service times.
We begin by recalling or defining the following notation. Job
ii refers to the
iith job to arrive at the queue.
As usual, we assume that a steady state solution exists; i.e.,
the arrival rate is less than the service rate.
-
X
i
X
i
- r.v. for service time of job
ii
-
X¯=E
X
i
X
X
i
-
X2¯=E
X
i
2
X
2
X
i
2
-
W
i
W
i
- r.v. for time job ii spends
waiting in queue before beginning service
-
W
i
¯=E
W
i
W
i
W
i
-
W=limi→∞
W
i
¯
W
i
W
i
-
N
i
N
i
- r.v. for number of jobs in the queue when job
ii arrives
-
N
i
¯=E
N
i
N
i
N
i
-
N
Q
=limi→∞
N
i
¯
N
Q
i
N
i
-
R
i
R
i
- r.v. for residual service time seen by job
ii (the amount of time job
ii must wait until a job in
service when ii arrives is
completed)
-
R
i
¯=E
R
i
R
i
R
i
-
R=limi→∞
R
i
¯
R
i
R
i
-
λλ - job arrival rate
-
ρ=λX¯
ρ
λ
X
- server utilization
When a job arrives at the queue, it must wait for the job in
service (if there is one) to complete. Since we are assuming
FCFS scheduling, it must also wait for all of the jobs which
arrived before it but which have not begun service to
complete.
W
i
=
R
i
+∑j=i-
N
i
i-1
X
j
W
i
R
i
j
i
N
i
i
1
X
j
R
i
R
i
will be 0 if the job arrives
when the queue is empty. Taking expectations,
W
i
¯=
R
i
¯+E∑j=i-
N
i
i-1E
X
j
|
N
i
=
R
i
¯+X¯
N
i
¯
W
i
R
i
j
i
N
i
i
1
N
i
X
j
R
i
X
N
i
This last step is valid because the number of jobs that are in
the queue at an arrival instant must be independent of the
service times of jobs that have not been serviced yet. We can
take
lim
i
→
∞
lim
i
→
∞
of both sides of this equation to obtain
W=R+X¯
N
Q
W
R
X
N
Q
From Little's Theorem,
N
Q
=λW
N
Q
λ
W
Substituting this into the expression for
WW gives
W=R+X¯λW=R+ρW=R1-ρ
W
R
X
λ
W
R
ρ
W
R
1
ρ
To determine
RR, we could make
use of a well-known result which relates the principal moments
R
i
n¯=E
R
i
n
R
i
n
R
i
n
of the residual time r.v. to the moments
X
i
n¯=E
X
i
n
X
i
n
X
i
n
of the service time r.v.:
R
i
n¯=
X
i
n+1¯n+1
X
i
¯
R
i
n
X
i
n
1
n
1
X
i
However, we can also find RR
directly by looking at a plot of the residual service time
r.v. as a function of tt. Define
the following functions:
-
rτ
r
τ
- the residual service time of the customer in
service at time ττ (this
will be 0 if no customer is in service)
-
Mt
M
t
- the number of service completions in the
interval
0t
0
t
; we are interested only in
tt such that
rt=0
r
t
0
.
The
figure below
illustrates how the residual service time changes over time.
When a job
ii begins service, its
residual service time starts at
X
i
X
i
and falls linearly (with slope -1) to 0.
The time average of
rτ
r
τ
in the interval
0t
0
t
is given by
1t∫0trτdτ=1t∑i=1Mt
X
i
22=12Mtt∑i=1Mt
X
i
2Mt
1
t
τ
0
t
r
τ
1
t
i
1
M
t
X
i
2
2
1
2
M
t
t
i
1
M
t
X
i
2
M
t
(1)
limt→∞1t∫0trτdτ=12limt→∞Mttlimt→∞∑i=1Mt
X
i
2Mt
t
1
t
τ
0
t
r
τ
1
2
t
M
t
t
t
i
1
M
t
X
i
2
M
t
(2)
These are time averages; however, the ensemble averages (means
of the steady state distributions) and time averages are
equal, giving us
R=λX2¯2
R
λ
X
2
2
Consequently,
W=λX2¯21-ρ
W
λ
X
2
2
1
ρ
One important variation on the M/G/1 queue is to allow the
server to take vacations - i.e., to be idle when
there is work to be done. The server goes idle at the end of
each busy period (when the queue becomes empty), and remains
idle for some random amount of time. If the queue is still
empty at the end of a vacation time, the server immediately
starts another vacation; otherwise, the server begins a job
service time.
The analysis proceeds as for the M/G/1 queue, up to the point
at which we find an expression for the average waiting time:
W=R1-ρ
W
R
1
ρ
except that we must define RR to
be the mean residual service or vacation time, since a job
might arrive during another job's service time or during a
server vacation, and it will be delayed until the completion
of either. Define
-
V
i
V
i
- r.v. for the length of vacation
ii
-
V
i
¯=E
V
i
V
i
V
i
-
V=limi→∞
V
i
¯
V
i
V
i
-
Lt
L
t
- the number of vacations completed in the
interval
0t
0
t
Assume that vacation times are independent and identically
distributed, and are independent of job interarrival and
service times.
We will be interested in looking at the system only at some
time tt corresponding to the
completion of a service or a vacation. In the figure below, darker
triangles are service times and lighter ones are vacations.
Proceeding as before:
1t∫0trτdτ=1t∑i=1Mt
X
i
22+1t∑i=1Lt
V
i
22=12Mtt∑i=1Mt
X
i
2Mt+12Ltt∑i=1Lt
V
i
2Lt
1
t
τ
0
t
r
τ
1
t
i
1
M
t
X
i
2
2
1
t
i
1
L
t
V
i
2
2
1
2
M
t
t
i
1
M
t
X
i
2
M
t
1
2
L
t
t
i
1
L
t
V
i
2
L
t
(3)
Since
t1-ρLt=V¯
t
1
ρ
L
t
V
we can take the limit as
tt
approaches
∞ of the average
residual service time and use the equality of time and
ensemble averages to obtain
R=λX2¯2+1-ρV2¯2V¯
R
λ
X
2
2
1
ρ
V
2
2
V
Substituting this into the expression for the average waiting
time gives us
W=λX2¯21-ρ+V2¯2V¯
W
λ
X
2
2
1
ρ
V
2
2
V
