Queueing Networks with Infinite Virtual Queues An Example,

Queueing Networks with Infinite Virtual Queues An Example,

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

Recently Viewed Presentations

  • Inside the Mind of…

    Inside the Mind of…

    A Little about the Man Himself. Born in 1916 in Wales to Norwegian Parents, Harald and Sofie. Attended Boarding School in Britain. In 1929, he attended Repton School where Cadbury, the chocolate company, would send boxes of chocolates to the...
  • Chapter 9: Reformation & Late Renaissance

    Chapter 9: Reformation & Late Renaissance

    The Late Renaissance in Italy & Spain. Baroque. This style was developed by DomenikoTheotocopoulos, El Greco. This style is defined as having a synthesis of mannerism and the style associated with the late Renaissance.
  • The Geography of Language

    The Geography of Language

    Language use is flexible. In code switching, people use different language depending on context. Language shifts occur as people move to different language regions. Language use is bound up with national identity as national languages are crated and maintained. Language...
  • Monogastric Production Swine Section

    Monogastric Production Swine Section

    Monogastric Production Swine Section Inventory of Hogs and Pigs June 1, 2004 Inventory of Hogs and Pigs June 1, 2004 Top Ten Hog States 1st Iowa (15,900,000 hd) 2nd North Carolina (10,100,000) 3rd Minnesota (6,500,000) 4th Illinois (3,950,000) 5th Indiana...
  • Geologic Time Scale Spring 2015 8 th Grade

    Geologic Time Scale Spring 2015 8 th Grade

    Early land plants included simple mosses, ferns, and then cone-bearing plants. By the end of the era, seed plants were common. The massextinctionthat ended the era caused most marine invertebrates as well as amphibians to disappear. Paleozoic Era
  • Diapositiva 1 - WordPress.com

    Diapositiva 1 - WordPress.com

    - Layered and fluffy-not thought of as rain clouds-clouds at lower altitudes. Stratus-gray in colour ... -looks like cauliflower at the top. Cumulonimbus-very thick, up to 13,000 . metres. in height-violent, circulating air currents-can produce baseball size hail
  • Russia, China, and the Birth of Communism

    Russia, China, and the Birth of Communism

    Absolute Rulers of Russia. Peter the Great and Russia. Romanov. dynasty begins in 1613. Romanovs strengthened government by passing a . law. code and putting down . revolts. which paved way for absolute rule of Czar . Peter. I. Peter...
  • Media Off-screen

    Media Off-screen

    (Jean-Louis Baudry, Christian Metz) cinema as an institution that creates an "ideal, transcendental viewing subject". (Baudry, p. 79) introduction of Lacan (mirror stage - the importance of screen-spectator relationship), does not address gender and sexuality (the viewing subject is assumed...