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)
Congestion pricing The basic observation The congestion costs due to any specific user have 2 components: (1)Cost of delay to that user(internal cost) (2) Cost of delay to all other users caused by that user (external cost) At congested airports(and congested facilities, in general) this second component can be very large A congestion toll can be imposed to force users to experience this cost component (to internalize the external costs
Congestion pricing: The basic observation • The congestion costs due to any specific user have 2 components: (1) Cost of delay to that user (internal cost) (2) Cost of delay to all other users caused by that user (external cost) • At congested airports (and congested facilities, in general) this second component can be very large • A congestion toll can be imposed to force users to experience this cost component (to “internalize the external costs”)
Economic principle Optimal use of a transportation facility cannot be achieved unless each additional (marginal) user pays for all the additional costs that this user imposes on all other users and on the facility itself. A congestion toll not only contributes to maximizing social economic welfare, but is also necessary to reach such a result. (Vickrey, 1967, 1969; Carlin+ Park, 1970)
Economic principle Optimal use of a transportation facility cannot be achieved unless each additional (marginal) user pays for all the additional costs that this user imposes on all other users and on the facility itself. A congestion toll not only contributes to maximizing social economic welfare, but is also necessary to reach such a result. (Vickrey, 1967, 1969; Carlin + Park, 1970)
Two hard technical problems o In practice it is very hard to: (1)Estimate external marginal delay costs (extensive data analysis or difficult simulation is typically needed) (2)Determine equilibrium congestion tolls (trial- and error approach that may take long time to converge is used sometimes) o Queuing theory has much to offer(especially with regards to the first problem) under certain conditions
Two hard technical problems · In practice it is very hard to: (1) Estimate external marginal delay costs (extensive data analysis or difficult simulation is typically needed); (2) Determine equilibrium congestion tolls (trialand error approach that may take long time to converge is used sometimes). · Queuing theory has much to offer (especially with regards to the first problem) under certain conditions
Congestion pricing and queuing theory Consider a queuing facility with a single type of customer in steady-state. Let c= delay cost per unit time per customer C=total cost of delay per unit time incurred in the system at equilibrium C=cL=chW and the marginal delay cost, MC, imposed by an additional ("marginal")customer is given by Mc: dc cw+c1 d1 d入
Congestion pricing and queuing theory q Wq C = cL = cl MC = dC dl = c Wq + cl dWq dl Consider a queuing facility with a single type of customer in steady-state. Let c = delay cost per unit time per customer C = total cost of delay per unit time incurred in the system at equilibrium and the marginal delay cost, MC , imposed by an additional (“marginal”) customer is given by:
Congestion pricing and queuing theory(2) Note that the first term on the right is the internal cost"experienced by the marginal customer and the second term is the"external cost"(s)he imposes These ideas can be extended to cases with multiple types of customers and to systems with priorities
Congestion pricing and queuing theory (2) • Note that the first term on the right is the “internal cost” experienced by the marginal customer and the second term is the “external cost” (s)he imposes! • These ideas can be extended to cases with multiple types of customers and to systems with priorities
