Queuing Theory

Defining Qualities

trade offs
• cost of waiting
• cost of providing service

inherent randomness
• arrivals
• service time
• without randomness we have an engineering problem in capacity and scheduling

Introductory Examples

people waiting
• for tickets at a box office each gets his own ticket one person gets tickets for a group
• in a bank for a teller with one line and several tellers
• at a grocery store in several check out lines, and jockeying
• for Star Tours at Disneyland, then reneging
• for medical treatment in a hospital emergency room

machines waiting for repair
• office copiers under maintenance contract
• factory equipment

telephone calls waiting for
• switching and available lines
• service at the other end hanging up if busy waiting on hold

factory jobs waiting at several stages of production

cars waiting to get on the freeway

cases working their way through the court system

Description of Queuing Systems

calling population
• finite
• infinite

system structure
• servers
• queues

system discipline
• order of service
  • FIFO
  • LIFO
  • priority
    • rank as a property of the arriving unit
    • triage: priority assigned by the server
  • random
  • round robin
• queue behavior
  • balk or reject
  • renege
  • jockey
  • collude
  • be patient
• distribution of arrivals Poisson
• distribution of service times exponential
• notation A/B/s
  • A is a symbol for the type of arrival distribution
  • B is a symbol for the type of service distribution
  • s is the number of servers
  • additional parameters sometimes appear
  standard symbols
  • G for a general distribution
  • M for Poisson arrivals or exponential service times exponentially distributed service time means time already spent does not change the remaining time expected
  • D for a constant distribution, that is, deterministic

Operating Characteristics, that is, long term expected values

Lengths
• system, L
• queue, Lq

Waiting Time
• in the queue, Wq
• in service, 1/m
• in the system, that is, cycle time, W

Rates
• arrival, l
• service, m
• traffic density, r = l/m

Variances of the above

Probabilities
• utilization: P0, P1, , etc.

Total Cost
• waiting idle time people machines lost profit balking reneging
• providing service idle server time busy server time fixed and variable costs

Taking Action

Opportunities

• service
• calling population
• queue discipline
• randomness
• coordination

Procedure

Specify the Problem to be Solved

• time
• location
• population
• service

Formulas

Little's Flow

• L = lW
• Lq = lWq
• W = Wq + 1/m

M/M/1

• P0 = 1 - l/m = 1 - r
• W = 1/(m - l)
• L = l/(m - l)
• Wq = l/(m(m - l))
• Lq = l2/(m(m - l))

M/M/s

• P0 = (Sn=0s-1rn/n! + rs/s!(1-r/s)-1)-1
• Lq = P0rs+1/((s-1)!(s-r)2)

Blocked Lines Cleared

Initial Conditions versus Steady State some systems are slow to change form one condition to another an early overload can mask the eventual average condition

Examples

observed operating characteristics

Queues for Bank Tellers: one versus two

• l = 10 per hour
• m = 20 per hour
• P0 = 1/2
• W = 6/60 hours

• l = 20 per hour
• m = 20 per hour
• P0 = (2m - l)/(2m + l)= 1/3
• W = 4m/(4m2 - l2) = 4/60 hours

Post Office Exercise

Required:

• When can M/M/1 formulas be applied?
• If M/M/1 applies find average customers in the Post Office and average wait before being helped.
• What can management do to improve matters?

Blocked lines example from the text.

Mention L. L. Bean case

Ask the class how they might apply queuing theory to the courts.