Spatially Distributed Queues M/G/1 2 Servers N servers Approximations M/G/1 Ambulance (0,0) (0,Y 0 ) (X 0 ,0) Directions Of Travel X A Y A M/G/1 Ambulance (0,0) (0,Y 0 ) Directions Of Travel X A Y A (X 0 ,0) M/G/1 aAmbulance always returns home with each service; standard M/G/1 applies aBut suppose we have an emergency repair vehicle that travels directly from one customer to the next?…... M/G/1 S 1 of the 1st service time in a busy period S 2 of the 2nd λ ρ ,σ S 1 2 = expected value and variance,respectively, ,σ S 2 2 = expected value and variance,respectively, & all succeeding service times in a busy period S 2 < 1 =1 ? P 0 = fraction of time server is busy M/G/1 ρ = λS 1 1 ? λ(S 2 ? S 1 ) L = ρ + λ 2 1 ? λ(S 2 ? S 1 ) [ σ S 1 2 + S 1 2 + λ{S 1 (σ S 2 2 + S 2 2 ) ? S 2 (σ S 1 2 + S 1 2 ) 2(1 ? λ S 2 ) ] M/G/1 Little' s Law : Buy one,get three others for free! L = λW L q = λW q See the book, Eqs. (5.0) - (5.5) Two-Server “Hypercube” Queueing Model aDistinguishable servers aDifferent workloads (due to geography) aCan appear with or without queueing `With -- usually FCFS `Without -- usually means a backup contract service is in place A B-A B = “Service Region” Poisson Arrivals from any sub-region A A B-A λ(A)=λ 1 λ(B-A)=λ 2 B = “Service Region” λ = λ 1 + λ 2 Service Discipline a1st Dispatch Preference to ‘primary server’ aOtherwise, assign customer to other server, if available aOtherwise, job is ‘lost” (What happens in practice?) 1,0 0,0 1,1 0,1 1,0 0,0 0,1 λ 1,1 λ μ μ μ λ 2 λ 1 μ Balance of Flow Equations 1,0 λ 2 μ OK? 0,0 0,1 λ 1,1 λ μ μ λ 1 μ OK? Balance of Flow Equations P 00 (λ 1 + λ 2 ) = P 01 μ + P 10 μ P 01 (λ + μ) = P 11 μ + P 00 λ 1 Etc. P 00 +P 10 +P 01 +P 11 = 1 Workload and Imbalances aρ 1 = W 1 = P 01 + P 11 aρ 2 = W 2 = P 10 + P 11 aWorkload Imbalance = ?W = |W 1 -W 2 | To Obtain Travel Times, We Must Have Server Response Patterns af nj = fraction of dispatches that are server n to response area j aT n (C) = average time for server n to travel to a customer in region C aT(A) = average system-wide travel time, assuming that server 1’s primary response area is region A. Average System-Wide Travel Time T(A)=f 11 T 1 (A) + f 22 T 2 (B-A) +f 12 T 1 (B-A) + f 21 T 2 (A) Average System-Wide Travel Time T(A)=f 11 T 1 (A) + f 22 T 2 (B-A) +f 12 T 1 (B-A) + f 21 T 2 (A) Queueing Average System-Wide Travel Time T(A)=f 11 T 1 (A) + f 22 T 2 (B-A) +f 12 T 1 (B-A) + f 21 T 2 (A) Geometry How do we obtain the f nj ’s? aConsider a long time interval T af 12 =(# requests that assign unit 1 to area 2)/ (total # requests answered)aTotal # requests answered = (1-P 11 )λT aAverage # requests that are “server 1 to area 2” is λ 2 TP 10 . Why? aTherefore f 12 =(λ 2 TP 10 / [1-P 11 ]λT) = {λ 2 /(1-P 11 )λ)} P 10 How do we generalize this to N servers? Rectangular City Example x y -1 +1 x=0.75 x=-0.25 x y -1 +1 x=-0.25 x=0.75 * w 1-w High Demand Area: 50% workload Rectangular City Example Equal travel time Boundary line