Transcript Queing2003 final exam

2003 Fall Queuing Theory Final Exam (Time limit：2 hours)
1.
(10%) Let two independent, exponentially distributed random
variables x and t denote the service time and the inter-arrival time
of a system with parameters  and  , respectively. And y denotes
the busy period length of the system.
Define event D: { x < t } and event A: { x > t } .
(a)
(b)
(c)
(d)
(e)
Derive p(Z  z ) , where Z = min[ x , t ] . (2%)
Derive E [Z ] . (2%)
Derive p(A) and p(D) . (2%)
Derive E [ y ] in terms of p(A), p(D) and E [Z ] . (2%)
Derive E [ y ] in terms of  and  . (2%)
2.
(20%) Consider an M/M/1 queuing system with parameters 
and  . At each of the arrival instants one new customer will enter
the system with probability ½ or two new customers will enter
simultaneously with probability ½.
(a) Draw the state-transition-rate diagram for this system. (5%)
(b) Using the method of non-nearest-neighbor systems write down the
equilibrium equations for pk. (5%)
(c) Find P(z) and also evaluate any constants in this expression so
that P(z) is given in terms only of  and  . If possible eliminate
any common factors in the numerator and denominator of this
expression. (5%)
(d) From (c) find the expected number of customers in the system. (5%)
3.
(20%) There are 10 students and 4 TAs in the final exam of
Queuing Theory. The students are always busy doing one of the
two activities: writing (work state) or asking questions (service
state); no other activities are allowed. Each student is initially in
the work state for an exponential, rate  , period of time. Each
student then attempts to ask one of the TAs a question. If all TAs
are busy, then the student is blocked and returns to the work state.
Assume that the time each student takes to ask a question is
exponentially distributed with rate  and then returns to the work
state :
(a) Define an appropriate state space for this service system. Draw a
state diagram for this system showing all transition rates. (4%)
(b) Write the balance equations for the system. (4%)
(c) Specify a method of computing the ergodic blocking probability for
the system—that is, the proportion of attempts to join the service
system that will be blocked—in terms of the system parameters
and the ergodic state probabilities. (4%)
(d) Specify a formula to compute the average question generation rate.
(4%)
(e) Let  = 1/3 questions per minute. Compute the blocking probability
as a function of  for   (0,30). (4%)
4. (20%) Consider an M/G/1 system in which time is divided into intervals of length q
sec each. Assume that arrivals are Bernoulli, that is,
P [1 arrival in any int erval ]  q
P [0 arrivals in any int erval ]  1- q
P [ 1 arrival in any int erval ]  0
Assume that a customer's service time x is some multiple of q sec such that
P [service time  nq sec]  g n n  0,1,2,...
(a ) Find E[number of arrivals in an interval].
(b ) Find the average arrival rate. (2%)
(2%)
(c ) Express E [ x ]  x and E [ x( x - q )]  x 2 - xq in terms of the moments
of the gn distribution ( i.e., let g
k


k
n
 gn )
(3%)
m 0
(d ) Find y mn  P[m customers arrive in nq sec].
(3%)
(e ) Let v m  P[m customers arrive during the service of a customer] and let
V (x) 

v
m 0
and G( z ) 
mz
m

g
m 0
m
z
m
Express V(z) in terms of G(z) and the system parameters λ and q.
(5%)
(f ) Find the mean number of arrivals during a customer service time from (e).
(5%)
5.
(25%) Consider the M/M/2 queuing system which has Poisson
arrivals, exponential service, two parallel servers and an infinite
waiting room capacity.
(a) Determine the expected first passage time from state 2 to state 1.
(4%)
(b) Determine the expected length of the busy period for the ordinary
M/M/2 system using the result from (a). (4%)
(c) Define c as the length of time between successive entries into
busy periods, that is , as the length of one busy / idle cycle.
Determine the probability that the system is idle at an arbitrary
point in time. Determine the probability that there is exactly one
customer in the system. (4%)
(d) Determine the total expected amount of time the system spends in
state 1 during a busy period. (4%)
(e) Check (c) and (d) using classical birth-death analysis. (4%)
(f) Determine the expected sojourn time E [s ] for an arbitrary
customer by the Little’s Formula. (5%)
6.
(15%) Let x denote a random period of time and Fx* (s ) is the
Laplace transform of Fx ( x ) . Let n(t ), t  0 be a Poisson process
with rate  and let v denote the number of arrivals from n(t ), t  0
occurred during the period of time x .
Derive the relationship between the Z transform of v , Fv* (z) , and
the Laplace transform of x .