460 An Introduction to Stochastic Modeling Hint: Let P kj (t) = Pr{D(t) = j|N(0) = k} and P j (t) = k P kj (t) = Pr{D(t) = j}. Use a first step analysis to show that P 0j (t + t) = ( t)P 1j (t) + [1 - ( t)] P 0j (t) + o( t), and for k = 1, 2, . . . , P kj (t + t) = µ( t)P k-1,j-1 (t) + ( t)P k+1,j (t) + [1 - ( + µ)( t)]P kj (t) + o(t). Then, use P j (t) = k k P kj (t) to establish a differential equation. Use the explicit form of k given in the problem. 9.2.6 Customers arrive at a service facility according to a Poisson process of rate . There is a single server, whose service times are exponentially distributed with parameter µ. Suppose that "gridlock" occurs whenever the total number of cus- tomers in the system exceeds a capacity C. What is the smallest capacity C that will keep the probability of gridlock, under the limiting distributing of queue length, below 0.001? Express your answer in terms of the traffic intensity = /µ. 9.2.7 Let X(t) be the number of customers in an M/M/ queueing system at time t. Suppose that X(0) = 0. (a) Derive the forward equations that are appropriate for this process by substi- tuting the birth and death parameters into Chapter 6, equation (6.24). (b) Show that M(t) = E[X(t)] satisfies the differential equation M (t) = - µM(t) by multiplying the jth forward equation by j and summing. (c) Solve for M(t). 9.3 General Service Time Distributions We continue to assume that the arrivals follow a Poisson process of rate . The suc- cessive customer service times Y 1 , Y 2 , . . . , however, are now allowed to follow an arbitrary distribution G(y) = Pr{Y k y} having a finite mean service time = E[Y k ]. The long run service rate is µ = 1/. Deterministic service times of an equal fixed duration are an important special case. 9.3.1 The M/G/1 System If arrivals to a queue follow a Poisson process, then the successive durations X k from the commencement of the kth busy period to the start of the next busy period form a renewal process. (A busy period is an uninterrupted duration when the queue is not empty. See Figure 9.3.) Each X k is composed of a busy portion B k and an idle portion I k . Then p 0 (t), the probability that the system is empty at time t, converges to t lim p 0 (t) = 0 = E[I 1 ] E[X 1 ] E[I 1 ] = E[I 1 ] + E[B 1 ] (9.20) by the renewal theorem (see "A Queueing Model" in Chapter 7, Section 7.5.3).