Homework 6 (The M/G/1 Queue) 40 Points The following BASIC code simulates the single-server queue with FIFO service. It generates the interarrival times and the service times for 100,000 customers; and it produces estimates of the server utilization, the fraction of customers who must wait in the queue, and the average waiting time. 100 FOR i = 1 TO 100000 110 IA = (generate interarrival time) 120 T = T + IA 130 W = W + X – IA 140 IF W < 0 THEN W = 0 150 IF W > 0 THEN c = c + 1 160 SW = SW + W 170 X = (generate service time) 180 SX = SX + X 190 NEXT i 200 PRINT SX/T, c/100000, SW/100000 Adapt the program and run it (using the language of your choice) for four different service-time (1) exponential service times, with mean service time E(X) = 0.5 (2) constant service time, X = 0.5 (3) X ~ U(0,1) (4) P(X=1/3) = 0.9, P(X=2)= 0.1 Assume that the interarrival times are exponentially distributed with mean value 0.625 (that is, Poisson arrivals with rate λ = 1. )6 . Fill in the table. For case (1), draw the graph of the theoretical distribution function of waiting times, Fw(t); and, on the same axes plot the simulation estimates at the values of t as t goes from –1 to 12 in increments of 1, and fill in the corresponding table. Theory for the M/G/1 queue: If λ is the arrival rate and X is the service time, then the server utilization is λE(X) E X   E X ρ = 1 if ( ) 1  if ( ) 1 λ λ < ≥ The probability that a customer must wait in the queue is P(W > 0 ) = ρ, and the mean waiting time is given by the famous Pollaczek-Khintchine formula, ρ E W ( ) = 1 − ( ) E X V X ⋅ ⋅ + 2 ρ  ( )  1  2 E X  ( )  .    In addition, if the service times are exponentially distributed, and the service is FIFO, then (t )    F (t) = − − ⋅ w ( ρ)  1 0 − ≥ 0 0 t 1 ρe (t ) E(X) < There is no simple formula for Fw(t) when the service times are not exponentially distributed. (Therefore, simulation is an important tool for the analysis of queues whose service times have any arbitrary specified distribution of service times; and the theoretical results for the special case of exponential service times are important because they can be used to check the logic and accuracy of the simulation.) ρ P(W > 0) P(W > 0.5) E(W) X theory simulation theory simulation theory simulation theory simulation 2 NA 3 NA 4 NA Fw(t) t theory simulation -1 0 1 2 3 4 5 6 7 8 9 10