Queuing Systems: Lecture 5 Amedeo odoni October 22. 2001
Queuing Systems: Lecture 5 Amedeo R. Odoni October 22, 2001
Quiz #1: October 29 Open book, 85 minutes(start 10: 30) Chapter 4 coverage: Sections 4. 1through 4. 7(inclusive); Section 4.9(skim through 4.9.4)[Up to lecture of 10/22 Review Problem set 3 Review some old quizzes Prof. Barnett: Quiz review today Odoni: Office Hours, Friday, 1: 30-3: 00
Quiz #1: October 29 • Open book, 85 minutes (start 10:30) • Chapter 4 coverage: Sections 4.1through 4.7 (inclusive); Section 4.9 (skim through 4.9.4) [Up to lecture of 10/22] • Review Problem Set 3 • Review some old quizzes • Prof. Barnett: Quiz review today • Odoni: Office Hours, Friday, 1:30-3:00
Lecture outline Bounds for G/G/1 systems A numerical example Congestion pricing in transportation the fundamental ideas Congestion pricing and queuing theory Nu merical example Practical complications The LaGuardia Airport example
Lecture Outline • Bounds for G/G/1 systems • A numerical example • Congestion pricing in transportation: the fundamental ideas • Congestion pricing and queuing theory • Numerical example • Practical complications • The LaGuardia Airport example
A general upper bound for G/G/ systems A number of bounds have been obtained for more general cases(see Section 4.9) A good example is an upper bound for the waiting time at G/G/1 systems: λ(0+) 2(1-p) (p<1) where X and S are, respectively, the r.v.'s denoting inter arrival times and service times Under some fairly general conditions, such bounds can be tightened and perform extremely well
A general upper bound for G/G/1 systems • A number of bounds have been obtained for more general cases (see Section 4.9) • A good example is an upper bound for the waiting time at G/G/1 systems: (7) where X and S are, respectively, the r.v.’s denoting interarrival times and service times • Under some fairly general conditions, such bounds can be tightened and perform extremely well ( 1) 2 (1 ) ( ) 2 2 < × - × + £ r r l s X s S Wq
Better bounds for a( not so)special case For G/G/1 systems whose inter-arrival times have the property that for all non-negative values of to, FX、1.、1( what does this mean, intuitively?) it has been shown that. B <W,<B (0+0) (p<1) 2 2(1-p) Note that the upper and lower bounds in(8 differ by, at most, 1 n and that the percent difference between the upper and lower bounds decreases as p increases
Better bounds for a (not so) special case • For G/G/1 systems whose inter-arrival times have the property that for all non-negative values of t0 , l 1 [ | ] E X - t0 X > t0 £ it has been shown that: ( 1) 2 (1 ) ( ) 2 1 2 2 < × - × + £ £ = + - r r l s s l r X S B Wq B (what does this mean, intuitively?) • Note that the upper and lower bounds in (8) differ by, at most, 1/l and that the percent difference between the upper and lower bounds decreases as r increases! (8)