Queueing Networks with Infinite Virtual Queues An Example, An Application and a Fundamental Question Yoni Nazarathy (Supervisor: Prof. Gideon Weiss) University of Haifa 20 15 10 5 0 0 10 20 30 40 STUDENTS PROBABILITY DAY Weizmann Institute of Science March 28, 2007 Multi-Class Queueing Networks (Harrison 1988, Dai 1995,) Queues {1,..., K } {Qk (t ), t 0} K 6 6 Initial Queue Levels Qk (0) k 1 Routes kk ' (n) k , k ' kk ' (n) Pkk ' n n lim 1/4 Servers 2 5 3
4 3/4 {1,..., I } AI K { Aik } Aik {0,1} Network Dynamics Processing Durations S k (t ) S k (t ) 1 k t ' t mk lim Qk (t ) Qk (0) S k (Tk (t )) k ' k ( S k ' (Tk ' (t ))) k k ' Resource Allocation Tk (t ) (Scheduling) Tk (0) 0 A T (t ) T (s) t s ik k k s t k Yoni Nazarathy, University of Haifa, 2007 Tk (t ) only when Qk (t ) 0 2 INTRODUCING: Infinite Virtual Queues Regular Queue Qk (t ) : {0,1, 2,...} Infinite Virtual Queue Qk (t ) t Relative Queue Length: R (t )
2 . 5 Nominal Production Rate R (t ) R (0) S (T (t )) t Example Realization 2 1 . 5 1 0 . 5 5 1 0 1 5 2 0 0 . 5 1 Yoni Nazarathy, University of Haifa, 2007 3 MCQN+IVQ Queues {1,..., K } {Qk (t ), t 0} {Qk (t ), t 0} k 0 6 {Rk (t ), t 0} k Initial Queue Levels Qk (0) k {1,..., K } 0 Qk (0) k 0
1 Routes kk ' (n) k k ' 0 (n) lim kk ' Pkk ' n n 1/4 Servers 2 5 4 3/4 3 {1,..., I } AI K { Aik } Aik {0,1} Processing Durations S k (t ) k S k (t ) 1 k t ' t mk lim Network Dynamics Qk (t ) Qk (0) Sk (Tk (t )) k ' k ( Sk ' (Tk ' (t ))) 0 k ' Z k (t ) Rk (t ) Rk (0) Sk (Tk (t )) k t Resource Allocation (Scheduling) T (t ) k Tk (0) 0 A T (t ) T (s) t s ik k k s t k K 0 k K
Nominal Productio n Rates k Tk (t ) Yoni Nazarathy, University of Haifa, 2007 only when Qk (t ) 0 for k 0 4 An Example Yoni Nazarathy, University of Haifa, 2007 5 A Push-Pull Queueing System (Weiss, Kopzon 2002,2006) Server 2 Server 1 PUSH PULL 1 1 2 2 i 1 1 2 PULL 2 1 PUSH 1 1 2 1 1 , 2 2 Inherently Stable or 1 1 , 2 2 Inherently Unstable
Proportion of time server i allocates to Pulling on lim Z (t ) 0 i t a i l i ty z i b l i a t t t t ll U eS u t F a R uire uire q Req e R Fluid Solution: 11 (1 2 )1 2 2 (1 1 )1 1 1 ( 2 2 ) 12 12 2 2 ( 1 1 ) 12 12 Yoni Nazarathy, University of Haifa, 2007 1 11 2 2 2 6 Maximum Pressure (Dai, Lin 2005) Max-Pressure is a rate stable policy (even when =1). Push-Pull acts like a =1 System. As Proven by Dai and Lin, Max-Pressure is rate stable. But for the Push-Pull system Max-Pressure is not Positive Recurrent: Queue on Server 1
Queue on Server 2 Yoni Nazarathy, University of Haifa, 2007 7 Positive Recurrent Policies Exist!!! 1 1 , 2 2 1 1 , 2 2 Ko pz n2 Ko pz 2 on, We iss n2 1 1,5 2 1 0,3 2 2 0,2 2 2 2 1 1 0,0 1,0 1 1 2,0 1 1 3,0 1
1 4,0 1 n1 5,0 1 Yoni Nazarathy, University of Haifa, 2007 1 0,0 1 1 4,2 2 2 4,1 2 2 2 2 3,1 2 3,0 1 5,2 2 2 2 2 3,2 2 2,0 1,0 2 2 2,2
1 5,3 2 2 2 1 4,3 2 2,1 2 1 3,3 2 0,1 0,1 1 1 2 2 2 2 2,3 1 2 0,2 2 200 6 2 1 1,3 1 4,5 2,4 1 1 2 1
1,4 0,3 2 2,5 1 1 2 0,4 2 1 0,4 2 2 1 0,5 200 2 on, We iss 1 2 5,1 2 2 4,0 1 2 n1 5,0 1 1 8 An Application Yoni Nazarathy, University of Haifa, 2007 9 Near Optimal Control over a Finite Time Horizon
Finite Horizon Control of MCQN T Min Solution is intractable 3 Q (t )dt k 0 k 1 We is s, N aza r ath y2 007 Approximation Approach: 1) Approximate the problem using a fluid system. 2) Solve the fluid system (SCLP). 3) Track the fluid solution on-line (Using MCQN+IVQs). 4) Under proper scaling, the approach is asymptotically optimal. Yoni Nazarathy, University of Haifa, 2007 10 Fluid formulation Server 2 Server 1 T min q1 (t ) q2 (t ) q3 (t ) dt 3 0 2 t s.t. q1 (t ) q1 (0) u1 ( s)ds 0 t 1 t q2 (t ) q2 (0) u1 ( s)ds u2 ( s )ds 0
0 t t q3 (t ) q3 (0) u2 ( s)ds u3 ( s)ds 0 1 1 u1 (t ) u3 (t ) 1 1 3 0 t (0, T ) 1 u2 (t ) 1 2 u , q 0 This is a Separated Continuous Linear Program (SCLP) Yoni Nazarathy, University of Haifa, 2007 11 Fluid solution SCLP Bellman, Anderson, Pullan, Weiss. Piecewise linear solution. Simplex based algorithm, finds the optimal solution in a finite number of steps (Weiss). The Optimal Solution: Q3 (0) q3 (0) 15 q3 (t )20 Q2 (0) q2 (0) 1 Q1 (0) q1 (0) 8 1 3 1.0 2 0.25 T 40 15 q2 (t ) 10 5 q1 (t ) 0 0 10 Yoni Nazarathy, University of Haifa, 2007 20 30 40
12 4 Time Intervals 3 0 2 5 0 n {k | qk (t ) 0, t n } 2 0 n {k | qk (t ) 0, t n } 1 5 1 0 5 0 1 0 K 0n {} 2 0 {} K n {1, 2,3}{1, 2,3} 3 0 4 0 {2} {2,3} {1,3} {1} For each time interval, set a MCQN with Infinite Virtual Queues. 3 2 2 1 0 0 1 3 3 3 2
1 0 2 1 1 4 Yoni Nazarathy, University of Haifa, 2007 1 14 1 3 4 14 13 Now Con trol the M CQN+IVQ Maximu Using a R m Press ate Stabl u re (Dai, = 1 e Policy Lin) is su ch a pol icy , eve n when Yoni Nazarathy, University of Haifa, 2007 14 Example realizations, N={1,10,100} seed 1 N 1 seed 2 20 20 20
15 15 15 15 10 10 10 10 5 5 5 5 0 0 10 20 30 40 0 0 10 20 30 40 0 0 10 20 30 40 0 200 200 200 200 150
150 150 150 100 100 100 100 50 50 50 50 0 N 100 seed 4 20 0 N 10 seed 3 0 10 20 30 40 0 0 10 20 30 40 0 0 10 20 30 40
0 0 2000 2000 2000 2000 1500 1500 1500 1500 1000 1000 1000 1000 500 500 500 500 0 0 10 20 30 40 0 0 10 Yoni Nazarathy, University of Haifa, 2007 20 30 40 0 0 10
20 30 40 10 0 0 10 10 20 30 40 20 30 40 20 30 40 15 A Fundamental Question Yoni Nazarathy, University of Haifa, 2007 16 Is there a characterization of MCQN+IVQs that allows: Full Utilization of all the servers that have an IVQ. Stability of all finite queues. Proportional equality among production streams. ? Yoni Nazarathy, University of Haifa, 2007 17 Thank You Yoni Nazarathy, University of Haifa, 2007 18
