Consider an M/G/1 queueing system with last come, first served (LCFS) preemptive resume service. That is, customers arrive according to a Poisson process of rate λ. A newly arriving customer interrupts the customer in service and enters service itself. When a customer is finished, it leaves the system and the customer that had been interrupted by the departing customer resumes service from where it had left off. For example, if customer 1 arrives at time 0 and requires 2 units of service, and customer 2 arrives at time 1 and requires 1 unit of service, then customer 1 is served from time 0 to 1; customer 2 is served from time 1 to 2 and leaves the system, and then customer 1 completes service from time 2 to 3. Let Xi be the service time required by the ith customer; the Xi are IID rv s with expected value E [X]; they are independent of customer arrival times. Assume λ E [X] 1.
(a) Find the mean time between busy periods (i.e., the time until a new arrival occurs after the system becomes empty).
(b) Find the time-average fraction of time that the system is busy.
(c) Find the mean duration, E [B], of a busy period. Hint: Use (a) and (b).
(d) Explain briefly why the customer that starts a busy period remains in the system for the entire busy period; use this to find the expected system time of a customer given that that customer arrives when the system is empty.
(e) Is there any statistical dependence between the system time of a given customer (i.e., the time from the customer's arrival until departure) and the number of customers in the system when the given customer arrives?
(f) Show that a customer's expected system time is equal to E [B]. Hint: Look carefully at your answers to (d) and (e).
(g) Let C be the expected system time of a customer conditional on the service time X of that customer being 1. Find (in terms of C) the expected system time of a customer conditional on X = 2. (Hint: Compare a customer with X= 2 to two customers with X = 1 each.) Repeat for arbitrary X = x.
(h) Find the constant C. Hint: Use (f) and (g); do not do any tedious calculations.
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.