《土木与环境工程》（英文版） Topics in Queuing Theory

Queuing Systems: Lecture 1 Amedeo odoni October 10. 2001

Queuing Systems: Lecture 1 Amedeo R. Odoni October 10, 2001

Topics in Queuing Theory 9. Introduction to Queues: Little' s law: M/M/ 10. Markovian Birth-and-Death Queues 11. The M/G/1 Queue and Extensions 12. Priority Queues; State Representations 13. Congestion Pricing 14. Dynamic Behavior of Queues 15. Hypercube Queuing Model 16. The Queue Inference Engine; Psychology of Queues

Topics in Queuing Theory 9. Introduction to Queues; Little’s Law; M/M/1 10. Markovian Birth-and-Death Queues 11. The M/G/1 Queue and Extensions 12. Priority Queues; State Representations 13. Congestion Pricing 14. Dynamic Behavior of Queues 15. Hypercube Queuing Model 16. The Queue Inference Engine; Psychology of Queues

Lecture outline Introduction to queuing systems Conceptual representation of queuing systems Codes for queuing models Terminology and notation Little's Law and basic relationships Birth-and-death processes The M/M/1 queuing system State transition diagrams Steady-state probabilities

Lecture Outline • Introduction to queuing systems • Conceptual representation of queuing systems • Codes for queuing models • Terminology and notation • Little’s Law and basic relationships • Birth-and-death processes • The M/M/1 queuing system • State transition diagrams • Steady-state probabilities

Queues Queuing Theory is the branch of operations research concerned with waiting lines (delays/congestion A queuing system consists of a user source, a queue and a service facility with one or more identical parallel servers a queuing network is a set of interconnected queuing systems Fundamental parameters of a queuing system Demand rate Capacity(service rate Demand inter-arrival times Service times Queue capacity and discipline(finite VS infinite FIFO/FCFS, SIRO, LIFO, priorities) Myriad details(feedback effects, jockeying", etc.)

Queues • Queuing Theory is the branch of operations research concerned with waiting lines (delays/congestion) • A queuing system consists of a user source, a queue and a service facility with one or more identical parallel servers • A queuing network is a set of interconnected queuing systems • Fundamental parameters of a queuing system: Demand rate Capacity (service rate) Demand inter-arrival times Service times Queue capacity and discipline (finite vs. infinite; FIFO/FCFS, SIRO, LIFO, priorities) Myriad details (feedback effects, “jockeying”, etc.)

A Generic Queuing System servers Arrival point C Departure point at the system from the system C Qu ueue Source ofusers/ CCCCCC C customers CCc Arrivals rocess pre Size of Queue discipline and Service process Number of servers user source Queue capacity

A Generic Queuing System Source of users/ customers C C C C C C Queue C C C C C C C Servers Size of user source Arrivals process Queue discipline and Queue capacity Service process Number of servers Arrival point at the system Departure point from the system

Queuing network consisting of five queuing systems Queueing Queueing system system 2 Queueing Point where Point where QueueingOut system users make users merge →+(+)ssem a choice Queueing stem

Queuing network consisting of five queuing systems In Queueing system 1 Queueing system 5 Point where users make a choice Point where users merge + Queueing system 4 Queueing system 2 Queueing system 3 Out

Applications of Queuing Theory Some familiar queues: Airport check-in Automated Teller Machines(ATMs) Fast food restaurants On hold on an 800 phone line Urban intersection Toll booths Aircraft in a holding pattern Calls to the police or to utility companies Level-of-service (LOS) standards Economic analyses involving trade-offs among operating costs, capital investments and los

Applications of Queuing Theory • Some familiar queues: _ Airport check-in _ Automated Teller Machines (ATMs) _ Fast food restaurants _ On hold on an 800 phone line _ Urban intersection _ Toll booths _ Aircraft in a holding pattern _ Calls to the police or to utility companies • Level-of-service (LOS) standards • Economic analyses involving trade-offs among operating costs, capital investments and LOS

Queuing Models Can Be Essential in Analysis of Capital Investments Cost Total cost Optimal Cost of building the capacity Cost of losses due to waiting “ Optim” capacity Airport Capacity

Queuing Models Can Be Essential in Analysis of Capital Investments Cost Airport Capacity Cost of building the capacity Total cost Cost of losses due to waiting “Optimal” capacity Optimal cost

Strengths and Weaknesses of Queuing Theory Queuing models necessarily involve approximations and simplification of reality Results give a sense of order of magnitude, changes relative to a baseline, promising directions in which to move Closed-form results essentially limited to"steady state"conditions and derived primarily(but not solely for birth-and-death systems and"phase"systems Some useful bounds for more general systems at steady state Numerical solutions increasingly viable for dynamic systems

Strengths and Weaknesses of Queuing Theory • Queuing models necessarily involve approximations and simplification of reality • Results give a sense of order of magnitude, changes relative to a baseline, promising directions in which to move • Closed-form results essentially limited to “steady state” conditions and derived primarily (but not solely) for birth-and-death systems and “phase” systems • Some useful bounds for more general systems at steady state • Numerical solutions increasingly viable for dynamic systems

A Code for Queuing Models ABIm Distribution of Queueing System service tme Number of servers // Customers Queue Distribution of CCCCCC interarrival time CCCc facility Some standard code letters for a and B: M: Negative exponential (M stands for memoryless D: Deterministic EK:kth-order Erlang distribution G: General distribution Model covered in this lecture: M/M/1

A Code for Queuing Models: A/B/m • Some standard code letters for A and B: _ M: Negative exponential (M stands for memoryless) _ D: Deterministic _ Ek :kth-order Erlang distribution _ G: General distribution • Model covered in this lecture: M/M/1 C C C C C C C C C C S S S S Service facility Queue Customers Queueing System – / – / – Distribution of interarrival time Distribution of service time Number of servers