< previous page	page_751	next page >
Page 751 M/G/1 Queues The derivation of the M/G/1 is generally straightforward, but somewhat distracting in the context of chapter 6. We present a (somewhat) informal derivation here, originally based on the work of Kendall [160]. There are many variations of the derivation, e.g. [166, 169]. We follow a simplified derivation from Goode and Machol [106]. We define the following random variables: ti = Time between successive departures i and i - 1 ri = Number of arrivals during a time interval ti ni = Queue length, including item in service at the end of ti We write the expection (mean) of each of the preceding as E(ti) = E(t), E(ri) = E(r,) E(ni) = E(n.) Also recall that The derivation assumes that r < 1 and that the process is stationaryi.e., statistically invariant over time. For our purposes, this means where p(n) is the probability of a queue size of n. Thus, E(n) is not a function of time (E(n1) = E(n2)). The requirement that r < 1 is a necessary result of stationarity. If r > 1, the queue size would grow as a function of time. Now consider items C1, C2 awaiting service at the moment that item C0 completes service. We designate the queue length (including the item in service) after C0 leaves as n0. Suppose it takes time T1 for the next item (C1) to be served. The number of items that arrive when C1 is being served is r1. When C1 completes service and departs, the queue length will be n1. Now n1 = n0 + r1 - 1.
< previous page	page_751	next page >