Queuing Theory

Queuing Theory Chapter 10

Why Study Queues? Standing in Line Costs $$$ ◆ We loose customers ◆ We waste employee time ◆ We “bottleneck” production processes ■ Eliminating Lines Costs $$$ ◆ We have to have more servers or shorter service times ■ So what’s the best trade-off? ■

Components of Queuing Process ■

Arrivals (Random)

■

Servers (Random)

■

Waiting Lines or Queues ◆ Discipline: First Come, First Served (FCFS), LCFS, etc.

Basic Structures Channel = Servers Phase = Steps in Service ■ Single Channel, Single Phase * ■ Multiple Channel, Single Phase ■ Single Channel, Multiple Phase ■ Multiple Channel, Multiple Phase ■ Other

Costs of a Queue

Total Cost

cost $

Service Costs

Waiting Costs

Level of Service

Operating Characteristics ■

Probability of the Service being idle ◆ No units in the system P0

■

Probability of some specified number of customers (units) are in the system ◆ Pn

■

Mean (expected) waiting time for each customer (W for total or Wq in queue)

Mean (expected) number in the system ◆ L ■ Mean (expected) number in the queue ◆ Lq ■

Model Assumptions ■

Arrival Distribution ◆ Most Commonly a Poisson Distribution ◆ Discrete Distribution (See page 474)

P(r) = e - λ (λ)r r!

Where: r = Number of arrivals P(r) = Probability of r arrivals λ = Mean arrival rate e = 2.71828 (base of natural log) r! = r factoral ( r ) (r-1)(r-2)(r-3)…..

Mean Time Between Arrives (More Assumptions) ■

Negative exponential distribution with mean of 1 / λ

■

Example: If mean arrival rate is 2 per hour then the mean time between arrivals is 1 / λ or 1 / 2 hours or 30 minutes

Distribution of Service Times (More Assumptions) ■

Most commonly negative exponential probability density function ◆ Area under the curve (See page 475)

f(t) = µ e -µ t

When: t = Service Times f(t) = probability density function t µ = mean service rate 1 / µ = mean service time e = 2.71828 (base of natural log)

Other Issues Infinite vs. Finite Calling Population ■ Infinite vs. Finite Queue Length ■ Steady State vs. Transient System ■ Arrival Rate vs. Service Rate ◆ Ratio of λ / µ will be less then one or the queue expands uncontrollably ◆ Exponential relationship (see page 478) ■

Queuing Notation ■

Written: (a/b/c) (d/e/f)

■

a = arrival dist b = service dist c = # of servers d = queue discipline e = max # in queue f = size of calling pop

■ ■ ■ ■ ■

■

Distributions ◆ M = Poisson ◆ D = Deterministic ◆ Ek = Erlang ◆ G = General

Example (M/M/1) (FCFS/inf/inf) ■

Single-Channel, Single-Phase (M/M/1) Formulas ■

Probability of no units in the system Po = 1 - λ / µ

Probability of n units in the system Pn = (λ /µ)n * (1 - λ /µ) ■ Mean # of units in system L = λ / (µ − λ) ■ Mean # of units in the queue Lq = λ 2 / µ ( µ − λ ) ■

(M/M/1) Formulas (Con’t) Mean time in the system W=1/(µ−λ) ■ Mean time in the queue Wq = λ / µ ( µ − λ ) ■

Service Facility Utilization p=λ/µ ■ Service Facility Idle Time I = 1 − λ /µ ■

FAX (or copier) Example Employees arrive at a rate of 20 per hour ◆ Assume a Poisson Distribution ■ Average time at machine is 2 minutes ◆ Assume a Negative Exponential Dist. ◆ 1/ µ ■ One Machine with One Line ■

(M/M/1) (FCFS/inf/inf) System

■

Mean # of units in system L = λ / (µ − λ) L = 20 / (30 - 20) L = 20 / 10 L = 2 employees in system

■

Mean # of units in the queue Lq = λ 2 / µ ( µ − λ ) Lq = 20 2 / 30 ( 30 − 20 ) Lq = 400 / 30 ( 10 ) Lq = 400 / 300 Lq = 1.33 employees in line

■

Mean time in the system W=1/(µ−λ) W = 1 / ( 30 − 20 ) W = 1 / 10 of an hour or W = 6 minutes each (on average) waiting for and using the machine

■

Mean time in the queue Wq = λ / µ ( µ − λ ) Wq = 20 / 30 ( 30 − 20 ) Wq = 20 / 30 ( 10 ) Wq = 20 / 300 Wq = 1 / 15th of an hour or Wq = 4 minutes each (on average) just waiting in line

Service Facility Utilization p=λ/µ p = 20 / 30 p = .67 or 67% or the time ■ Service Facility Idle Time I = 1 − λ /µ I = 1 − 20 / 30 Ι = 1 − .67 Ι = .33 or 33% of the time its idle ■

Should we hire an operator? An operator would reduce average service from 2 minutes to 1.5 minutes ■ The operator would cost $8.00 / hour ■ Average employee wage is $10.20 hours ■ L = λ / µ − λ = 20 / (40 -20) = 1 in system ■ The average number of employees in system is reduced from 2 to 1 ■

Resulting Costs ■

Alternative Service Waiting Cost Cost

Total Cost

No Oper.

$20.40 $40,800

0

$20.40

Annual Cost

2 * 10.20

With Oper. |

$8

$10.20

$18.20

$36,400

Annual Savings $ 4,400