Robert Graham Landrum








This report is dedicated to my parents and the memory of Robert Todd Lapsley Liston and of Charles Adair Bledsoe. These have been the architects of my education.













Presented to the Faculty of the Graduate School of

The University of Texas at Austin

in Partial Fulfillment

of the Requirements

for the Degree of







MAY 1993







The author would like to acknowledge the direction of Dr. David Fonken in the preparation of this report and the generousity of Dr. Klaus Bichteler in giving his time to this project. Dr. Georgia-Ann Klutke's contribution in reading this work is also appreciated.












                                                                                             – April 19, 1993



Table of Contents

Chapter One:  Introduction and Explanation of Notation..................................... 1

Chapter Two: The Queue Length in G/M/m Systems.......................................... 5

Chapter Three: M/G/1 (LCFS/I) Systems.......................................................... 12

Chapter Four: G/G/1 (LCFS/I) Systems............................................................ 20

Chapter Five: Conclusion.................................................................................. 29

Bibliography...................................................................................................... 31


Chapter One:  Introduction and Explanation of Notation

A classic example of a queue is a group of patrons lined up to purchase concert tickets. The two parts of a queueing system consist of a serving facility (e.g. the ticket booth) and a queueing facility (e.g. the line of concert goers). In general the queueing facility may consist of a number of queues as in a supermarket's checkout lines; like­wise the serving facility may have a number of servers. In this report models with one queue and mostly one server will be considered.

This kind of arrangement is often encountered; however there are other schemes that approximate other situations and have the advantage of easier calculation of rele­vant quantities. Once these calculations have been made, they may be transferred to a "normal" queue through a mathematical transformation. The difference in the models is in the queue discipline, which will be discussed presently.

The notation set out here is based on that of  Leonard Kleinrock.[1] The nth cus­tomer, designated by Cn where n 0, enters the system at tn . For cal­culation purposes t0 = 0. The waiting time wn is the time spent by Cn in the queue while xn is the associ­ated service time; furthermore the total system time for Cn is calculated as sn =  wn + xn. The difference tn = tn - tn-1 is the interarrival time between Cn-1 and   Cn. For most purposes the tn's and the xn's are considered to be independent. Now we may define


qn        =    the number of customers in the system just after Cn departs.[2]

q'n              =    the number of customers in the system just before Cn ar­rives.[3]


For each n the random variables tn and xn are the associated with the distribution func­tions An(t) and Bn(x) , and these values are the basis for the probabilistic nature of the setup. The related probability density functions (pdf's) are an(t) and bn(x) respec­tively.

If a sequence of random variables converges (in probability) as n , then the corre­spond­ing limiting variable is denoted with a tilde: . Limiting distribution functions and their pdf's are written without a subscript e. g. A(t) and a(t).

The following variables may now be defined for the number of customers in the system:

pk     =       [4]

dk     =     Pr()

rk     =     Pr()  [5]

For and  set . Define the utilization factor where m is the number of servers. Since it is the ratio of the average arrival rate to the average service rate for the system, 0 r 1 in order  for an equilibrium state to oc­cur; otherwise the servers will not be able to handle incoming customers fast enough.

The Laplace transform of the variable's pdf will be represented as


where H(y) = Pr(Y y) is a distribution function.[6] Similarly the z-transform – also called the generating function – for a discrete random variable is

                                               .                                 (1.2)

Here hn = Pr(Y = n).[7]

In order to be classified succinctly, queues are designated with the form A/B/m where A and B stand for the distributions of the interarrival and service times respec­tively and m is the number of servers in the service facility. The distributions are de­noted as follows:

G: General

M: (for Markov process) Exponential 

Er: r-stage Erlangian

HR: R-stage hyperexponential

D: Deterministic


A M/HR/2 queue, for example, has exponentially distributed interarrival times, services with an R-stage hyperexponential distribution, and employs two servers.[8]

How a customer progresses through the system is described by the queue disci­pline. The most common process is the first-come-first-served (FCFS) discipline where the next customer to be served is the one that has been in the queue the longest. This is like the concert goers buying tickets. An alter­nate scheme is called the last-come-first-served (LCFS) discipline. Here the next customer for service is the  latest. (This is re­ally a stack but  will be called a queue.)

In this report the last-come-first-served queue discipline with preemptive resume will be explored usually for queues with one server. Its designation will be LCFS/I where the "I" stands for "interrupt." Upon the arrival of a cus­tomer into such a system, the customer in service leaves the server immediately and enters the queue; the new customer takes up the position with the server. If the cus­tomer with the server com­pletes his service, he leaves the system, and the last customer to have entered the queue returns to the server. This will be the customer who was in service when the now de­parting one arrived.[9]

This report proceeds with a discussion of the intrinsic geometric nature of G/M/m queues. M/G/1 (LCFS/I) models are then explored through an intuitive interpretation of  Beneš's inversion of the Polleczek-Khinchin Transform Equation. The last topic is G/G/1 (LCFS/I) systems with an expansion of the techniques used for the M/G/1 ar­rangement.



Chapter Two: The Queue Length in G/M/m Systems

In this chapter we will discuss the geometric distribution of queue length under an arbi­trary queueing discipline, but the service time will be assumed to be exponentially distrib­uted.

The mathematical basis for this analysis is the semi-Markov chain. Let Xn be a random variable that is paired with a time Tn where Ti < Tj for i < j. The sequence {Xn,Tn} is then a semi-Markov chain[10] if



Setting  t to leaves



To be as general as possible, it will be assumed that there are m servers.  The de­velopment follows that of Kleinrock.[11]

The random variables of the sequence q'n} form a semi-Markov chain, and the rela­tionship between successive pairs is easily established:


                                           q'n+1 = q'n + 1 - v'n+1            (n 0).                                                           (2.3)


Here v'n+1 is the number of customers who finish being served and leave between the arrivals of Cn and Cn+1 . The transition probabilities are designated


                                                   pij =   Pr(q'n+1 = j | q'n = i)                                     (2.4)

or equivalently

                             pij = Pr(i + 1 - j  customers leave during tn+1 | q'n = i).                (2.5)


With the v'n's being nonnegative, it follows immediately that


                                                   pij = 0     for    j > i + 1.                                     (2.6)           

We will concentrate on the situation where i m. Since the service time is expo­nentially distributed,


                     .       (2.7)


Now pij may be calculated for  m j i + 1:



In this last equation the dependence on i and j is in the form i + 1 - j. Define n = i + 1 j, and set


                       .          (2.9)


bn is the probability that n customers finish service in an interarrival time given that all m servers are occupied. Let Ek be the event that there are k customers in the system, and define


ci(j)     =    the number of times that the state Ej is reached between suc­cessive visits to Ei.

sk       =    E( ck(k + 1) )                                    (k m – 1)

g         =    Pr( ck+ 1 (j) = 0,  j   k)                      (k m – 1)

           =    Pr( ck+ 1 (k) = 0)

Nk(t)   =    the number of times in (0, t) that an arriving customer finds the system in state Ek when the system starts at t = 0 with 0 customers.       


Note that g is the same regardless of the value of k. In order to see this, suppose that a sequence of transitions between states results in ck + 1(k) = 0 where k m – 1. Every such sequence can be matched one-to-one with a parallel sequence having the same relative transitions but starting with k + 2 customers in the initial system; further­more this parallel sequence satisfies ck + 2(k + 1) = 0 and has the same probability as the first. It is apparent that


                            Pr( ck+ 1 (k) = 0) = Pr( ck+ 2(k + 1) = 0)          k m – 1.             (2.10)


The variable sk may be thought of as the ratio of the times that the system is in state Ek + 1 to the times it is in state Ek. It follows that

                                                .                                (2.11)

If a(t) is the number of customers that have entered the system in (0, t), then

                                                     ;                                     (2.12)


                                          .                           (2.13)


From Equation 2.1 it is apparent that if a system goes from a state Ek to Ek' (< k'), it can only do so by rising through successive states; thus if a system in state Ek loses customers before a new customer can arrive, it must pass through Ek before reaching Ek + 1. In such a case ck(k + 1) = 0. This indicates that


                                                    Pr(ck(k + 1) > 0) = b0.                                     (2.14)


We may now calculate


          Pr(ck(k + 1) = n)  =   Pr(ck(k + 1) > 0)   [Pr(ck + 1(k) = 0)]n – 1 Pr(ck + 1(k) > 0)

                                      =  b0gn – 1(1 – g),                                                              (2.15)



which reduces to

                                                .                                (2.17)


Since the right side of this equation does not depend on k, we may drop the subscript:      for  k m – 1.                                                                (2.18)                                                                     

From Equation 2.10

                                                    rk+ 1 = srk     k m – 1                                     (2.19)


                                                   rk + 1 = Ksk     k m – 1.                                   (2.20)


Here is the geometric relation, but now we need to find K and s. With rk being an equilibrium probability, the vector r = (r0, r1, r2, r3, . . .) is a solution of the equation rP where P = (pij). Explicitly, when all servers are known to be busy,



Solving for s, we get

                                                      ,                                      (2.22)

which is equivalent to



By solving the last equation for a value in (0, 1), s may be determined. K  then follows from the fact that .


Theorem: The length of the queue proper given that an arriving customer finds all servers busy is geometrically distributed.


Proof. Let Q be the event that an incoming customer must enter the queue; then





This is the desired result.


Theorem: The number of customers in a G/M/1 system is geometrically distributed.





which may be solved to yield


                                                            K  = 1 – s.                                             (2.27)


The intended result  rk = (1 – s)sk easily follows.


The geometric nature of these systems comes from the circumstance of  b0 , g, and thus sk being independent of k. As was shown earlier, g was developed without appealing to the underlying probability distributions. On the other hand, the independ­ence of  b0 from k was evidenced in Equation 2.8 which was derived from the Poisson distribution of  departing customers: the exponential service times are central to this ar­gument although there is no need for a special queueing dis­cipline.



Chapter Three: M/G/1 (LCFS/I) Systems

Although the material in this chapter is less general than that in the next chapter, it provides an insight into what is actually occurring with the LCFS/I discipline.

The value of the exponential distribution is that it is memoryless – that is Pr(s+t |s) = Pr(> t).[12] In the G/M/m case this meant that only the time be­tween arrivals was needed to calculate the number of departures for that period: the time between the last departure and first arrival could be "forgotten." For M/G/1 sys­tems the situation is reversed: since the arrivals are exponentially distributed, the semi-Markov chain is established on the sequence {qn} of departure times.


3.1. Beneš's Inversion of the Pollaczek-Khinchin Formula for Waiting Time


For this section we need three distribution functions:


                                                        Q(t) = Pr()

                                                         S(t) = Pr()

                                                        W(t) = Pr()


 Q#(z) can be obtained from the Pollaczek-Khinchin Transform Equation:

                                       .[13]                          (3.1)


Another form of this generating function may be calculated using the FCFS dis­cipline. In this case all the qn customers in the system when Cn leaves arrive during Cn's system time. Since interarrival times are exponentially distributed, qn has a Poisson distribution:


                                            .                               (3.2)


Integrating with respect to s and taking the limit as , we get

                                              .                                 (3.3)


Now we calculate[14]



Setting s = l - lz and combining Equations 3.1 and 3.4, we get

                                           .                              (3.5)


The equation  leads to


                                                      S*(s) = W*(s)B*(s),                                        (3.6)


which may be used to get



The residual life distribution for the service time is

                                                    ,                                      (3.8)


                                                   ;[15]                                   (3.9)





If  is the k-fold convolution of , set

                                                   ;                                   (3.11)


                                               .[16]                               (3.12)


3.2. An Attempt to Explain the Formula Directly with a FCFS Discipline


From the results in Chapter Two one may calculate that rk = (1 – r)rk for M/M/1  queues; also since in this case,  is the probability that the sum of k service times is less than t. This suggests that the following interpretation of Equation 3.12 is plausible:

                                             .                             (3.13)


 Now consider a M/D/1 (FCFS) setup where , a constant. In this case


                                                          .                                           (3.14)


From the Pollaczek-Khinchin Transform Equation,

                                                   .                                   (3.15)

Expanding this in a Taylor series, one obtains the dk's as the respective coefficients of the zk 's. Since  changes by integer increments, rk = dk and the following table may be constructed[17]:



Clearly this is not the geometric distribution intimated in Equation 3.12; further­more  and B(t) do not generally coincide. Equation 3.12 was useful for calculat­ing purposes but did not seem to have an intuitive explanation.


3.3. Cooper and Niu's Explanation using LCFS/I


Equation 3.13, with a new interpretation for , was shown to be the correct ex­planation by Robert Cooper and Shun-Chen Niu in their 1986 article.[18] The core of their calculations is in the following theorem.


Theorem: The number of customers in a M/G/1 (LCFS/I) queue is geometrically dis­tributed with rk = (1 – r)rk.


Proof. Define


       =    the residual time for the service after being interrupted. It has distribution function .


A queueing system can only reach a state Ek directly either by beginning in Ek – 1 and having a customer arrive or by being in Ek + 1 and losing a customer. In the latter case when a last-come-first-served arrangement is used, the service time of  the cus­tomer then entering service is actually a continuation of the service period interrupted by the now departing customer: the new service interval is a residual one. We may now de­termine that



Note that dk is used as opposed to dk+1 because this random variable refers to the num­ber of customers after the departure from the k+1 state. A similar calculation yields



It now follows that



Since a departing customer leaves the system in the same exact condition as when he arrived, dk = rk; thus



Knowing that r0 = 1 –r and using the normalization condition, we find that



                                                         rk = (1 – r)rk.                                         (3.22)


Equation 3.21 may be rewritten as

                                                  ,                                  (3.23)

which being essentially Equation 3.9 –l is after all an arbitrary positive number – gives that .[19]

In order to understand , one needs to define the function U(t) which gives the work time that remains to be done by the server at time t. If




is the heavy side step function, then

                                                       .                                        (3.26)


U(t) is a nonnegative function that jumps up xn in height at each tn. From these points it descends with a slope of –1 until another jump occurs or until U(t) = 0. In the latter case it remains flat up to the point where a new customer arrives. The positive portions of the function represent the system's busy periods. The complementary idle periods are the segments where U(t) = 0.[20]




                                                             Figure 3.1


The form of U(t) does not depend on how the customers are served; however in the FCFS case the remaining work time just before a customer arrives is that cus­tomer's waiting time: . One may interpret  as the equilibrium remnant work time just before a customer arrives. It is now straightforward to show that  in a LCFS/I system, and Equation 3.13 then follows. Beneš's inversion of the Pollaczek-Khinchin Transform Equation, which was devel­oped from a FCFS discipline, is more closely related to a LCFS/I discipline.



Chapter Four: G/G/1 (LCFS/I) Systems

Without the exponential distribution analysis of queues becomes more difficult. Semi-Markov processes can not be used in the same way as they were used for the G/M/m model: besides the interarrival times the times between a preceding departure and an arrival become important. The study of G/G/1 queues centers on ascending ladder points.


4.1. Preliminaries



                                               ,                                 (4.1)


where q(t) is again the step function.

R(t) is a function with a  –1 slope that jumps up xn at each tn: it is similar to U(t) except that it descends below zero.[21] The values just before the jumps will be desig­nated , and the difference in successive peaks will be un = Un+1Un for n 0. It can be deduced from Equation 4.1 that un = xntn+1.[22]

Define a new sequence nk starting with n1 set such that  is the first peak to ex­ceed U0 = 0. Assign nk + 1 so that  is the first peak after with .  is the set of  ascending ladder indices.

In a stable queue r < 1 or 1/m - 1/l < 0. This equation implies that E[un] < 0, and consequently . The result is that there can only be a finite number of ascending ladder indices. Set K equal to this number, and designate s = Pr(K 1).

Suppose that R(t) reaches . Since the un's are independent identically distrib­uted random variables, the probability that there is a point of R(t) that exceeds  is the same as the probability that R(t) rises above 0; therefore


                           Pr(K k + 1) = Pr(K 1 ) Pr(K k) = sPr(K k).              (4.2)


This leads to


                                                   Pr(K = k)  =  (1 – s)sk.                                     (4.3)

For K = k, set

                                               ,                                 (4.4)


                                                                .                                                  (4.5)


The 's are also independent identically distributed random variables. They represent the idle times in the dual queue[23] where the service and interarrival distributions are swapped. Let F(x) =    Pr( x) and designate its nth convolu­tion with itself with


For the un's the common distribution function will be

                                        .                          (4.7)


It will be important to specify notation for the customers currently in the queue. If  0, then set  equal to the remaining service time of the ith customer still in the queue. The index i ranges from i = 1 for the customer that has been there longest to i = k for the most recent one.[24]


4.2. A Theorem by D. Fakinos


Theorem: In a G/G/1 (LCFS/I) system,


        where s and F(t) are defined in the previous section.[25]


Proof. Consider what is necessary for a stationary distribution:


 For k = 0 and n > 0,

                                  .                   (4.10)


In the limit as n this leads to



For k > 0 and n > 0,


which, in the limit, becomes



From the preliminary material it may be deduced that


which transforms into



The event  is really the event that for K = k,  and  given that U0 = 0. This may be restated as


This leads to



If the theorem is correct, Equation 4.8 must satisfy Equations 4.11 and 4.13. In this light Equation 4.13 becomes





which agrees with Equation 4.17. Equation 4.11 agrees with Equation 4.15 in the same way. It follows that Equation 4.8 is a stationary distribution for the system and holds true in the limit.

To show that this solution is unique, note that since r < 1, the state for q' = 0 is non-null persistent. The probability r0 = 1 - s is independent of the initial state; and when the queue reaches that state the succeeding condition of the system is independ­ent of preceding conditions. The queue is ergodic and can only assume the character of the given so­lution.


4.3 A Result Based on Cooper and Niu's Argument


Usually the semi-Markov process is established  solely on the set of arrival in­stances or solely on the set of depar­ture instances. Since arrivals and departures affect the server for a LCFS/I queue, a semi-Markov process can be set up incorporating both types of events. In this light let




In this type of system a customer need only "see" the customers who enter the queue after him. In fact he need only be concerned with the customers who immedi­ately interrupt his service and consequently "block" his "view" until they have finished all their service time. This suggests that changes in state do not depend on the actual queue length but may be described by the following probabilities:


                                    aa = Pr(arrival | the last event was an arrival)

                                    ad = Pr(arrival | the last event was a departure)

                                    da = Pr(departure | the last event was an arrival)               (4.21)

                                    dd = Pr(departure | the last event was a departure)


These are further described by


                                                              Table 4.1


Here  is the residual time of an interrupted interarrival period:

                                        [26]                         (4.22)

Consider the value of  at an arrival:

                                         .                         (4.23)


Using the same methods of Section 3.3, one gets






With this,






Comparing this with Equation 4.8, one sees that



This produces a method for calculating a constant that was previously defined abstractly.




Chapter Five: Conclusion

For M/G/1 (LCFS/I) , and Equation 4.29 becomes

                                   ,                     (5.1)


which agrees with Equation 3.21. This is only natural since the calculation of s is a generalization of the calculation of r.

Again s can be calculated using Equation 4.29:



Looking at this more closely, we see that aa, being the probability that the last change in the system was an arrival, is equivalently the probability that no departures have occurred in the preceding interarrival time. ad is then the event that the system, currently in state Ek, was last in state Ek+1. Since the system must pass through Ek when going from Ej, j < k, to Ek+1, ad is actually the probability that the system does not visit Ek-1 between successive visits to state Ek; thus in accordance with the G/M/1 case,

                                                      .                                         (5.3)


The material in the preceding chapter can also be used to generalize the formula for the waiting time as was developed in Chapter Three:



In form Equation 4.29 parallels the successive-state probability ratio of other queues with geometrically distributed length. In calculability it becomes useful in de­termining quantities like the waiting time distribution. Understanding the s of LCFS/I queues is being used to give information about G/G/1 FCFS systems.






Bhat, U. Narayan.  Elements of Applied Stochastic Processes, 2nd ed. New York: John Wiley & Sons, 1984.

Cooper, Robert B., and Niu, Shun-Chen.  "Beneš's Formula for M/G/1-FIFO 'Explained' by Preemptive-Resume LIFO." Journal of Applied Probability, 23 (1986)  550-554.

Fakinos, D.  "The G/G/1 Queueing System with a Particular Queue Discipline." Journal of the Royal Statistical Society, B 43 (1981)  190-196.

Kleinrock, Leonard.  Queueing Systems, Vol. 1 New York: Wiley-Interscience, 1975.





Robert Graham Landrum was born in Bristol, Tennessee, on August 9, 1966, the son of Mary Fisher Landrum, M.A. and Graham Gordon Landrum, Ph.D. After attending Tennessee High School, Bristol, Tennessee, he entered King College, also of the same town, in 1983. He attended Purdue University for the summer of 1985, and during the summer of 1986, he pursued research at Lowell Observatory. In May of 1987 he graduated from King College with the degree of Bachelor of Science. In September, 1987, he entered The Graduate School of The University of Texas at Austin.







Permanent Address:   2115 Edgemont Avenue

                                 Bristol, Tennessee








This report was typed by the author.



[1]Leonard Kleinrock, Queueing Systems, I (New York: Wiley-Interscience, 1975), pp. 10-18, 396-399.


[2]Kleinrock, p. 177.


[3]Kleinrock, p. 242.


[4]Kleinrock, p. 90.


[5]Kleinrock, p.176.


[6]Kleinrock, p. 339.


[7]Kleinrock, p. 327.


[8]Kleinrock, pp. viii-ix.


[9]D. Fakinos, "The G/G/1 Queuing System with a Particular Queue Discipline," Journal of the Royal Statistical Society B, 43 (1981) 190.


[10]U. Narayan Bhat, Elements of Applied Stochastic Processes, 2nd ed.  (New York: John Wiley & Sons, 1984), p. 290.


[11]Kleinrock, pp. 241-251.


[12]Kleinrock, p. 45.


[13]Kleinrock, p. 194.


[14]Kleinrock, pp. 196-198.


[15]Kleinrock, p. 172.


[16]Kleinrock, pp. 200-201.


[17]Kleinrock, p. 176.


[18]Robert B. Cooper and Shun-Chen Niu, "Beneš's Formula for M/G/1-FIFO 'Explained' by Preemptive-Resume LIFO," Journal of Applied Probability, 23 (1986) 550-554.


[19]Cooper and Niu, pp. 552-554.


[20]Kleinrock, pp. 206-208.


[21]Kleinrock, pp. 223-224.


[22]Kleinrock, pp. 277-278.


[23]Kleinrock, pp. 309-310.


[24]Fakinos, pp. 191-192.


[25]D. Fakinos, "The G/G/1 Queueing System with a Particular Queue Discipline," Journal of the Royal Statistical Society B, 43 (1981), pp. 190-196.


[26]Kleinrock p. 172.