• Author / Uploaded
• Muhammad Sandilaga

• Categories
• Distribución de veneno
• Teoría estadística
• Teoría de probabilidad
• Física y matemáticas
• Matemáticas

Citation preview

Queuing Theory Carles Sitompul

Syllables           

Some queuing terminology (22.1) Modeling arrival and service processes (22.2) Birth-Death processes (22.3) M/M/1/GD/∞/∞ queuing system and queuing optimization model (22.4) M/M/1/GD/c/∞ queuing system (22.5) M/M/s/GD/∞/∞ queuing system (22.6) M/G/∞/GD/∞/∞ and GI/G/∞/GD/∞/∞ models (22.7) M/G/1/GD/∞/∞ queuing system (22.8) Finite source models (22.9) Exponential Queues in series and open queuing networks (22.10) M/G/s/GD/s/∞ system (BCC) (22.11) *Chapter 20. 4th edition

Some queuing terminology

Input process  The input process is usually called the arrival process.  Arrivals are called customers.  We assume that no more than one arrival can occur at a given instant.

For a case like a restaurant, this is a very unrealistic assumption.  If more than one arrival can occur at a given instant, we say that bulk arrivals are allowed.  We assume that the arrival process is unaffected by the number of customers present in the system.  The arrival process may depend on the number of customers present:  when arrivals are drawn from a small population (finite source)

 when the rate at which customers arrive at the facility decreases when the

facility becomes too crowded (the customer has balked).

Output process  The output process is often called the service process.  We usually specify a probability distribution - the service

time distribution - which governs a customer’s service time.  We assume that the service time distribution is independent of the number of customers present.  We study two arrangements of servers: servers in parallel and servers in series

Queue discipline  The queue discipline describes the method used to    

determine the order in which customers are served. FCFS = First come first serve LCFS = Last come first serve SIRO = Service in random order Priority queuing discipline classifies each arrival into one of several categories. Each category is then given a priority level, and within each priority level, customers enter service on an FCFS basis.

Method used by arrival to join  The method that customers use to determine which line to

join.  When there are several lines, customers often join the shortest line.  Whether or not customers are allowed to switch, or jockey, between lines.  Jockeying may be permitted, but jockeying at a toll booth plaza is not recommended.

Modeling arrival and service processes

Modeling the arrival process  We assume that at most one arrival can occur at a

given instant of time.

ti = time at which i - th customer arrive

Ti = ti +1 − ti = i - th interarrival time

 We assume that the Ti’s are independent, continuous

random variables described by the random variable A.  A negative interarrival time is impossible  We also assume stationary interarrival times (often unrealistic).  We may often approximate reality by breaking the time of day into segments (each segment then has the stationary assumption).  Morning rush hour  Midday segment  Afternoon rush hour

 We assume that A has a density function a(t).

 Define 1/ λ = mean or average of interarrival time (hours per

arrival).

 λ = arrival rate (arrivals per hour)

 The most common choice for A is the exponential

distribution.

No memory property of the exponential distribution

 It implies that if we want to know the probability distribution of

the time until the next arrival, then it does not matter how long it has been since the last arrival.  For h = 4, t=5, t = 3, t=2, t=0

 This means that to predict future arrival patterns, we need not

keep track of how long it has been since the last arrival.

Relation between Poisson and Exponential distributions

 A discrete random variable N has a Poisson distribution with

parameter λ if, for n = 0, 1, 2, . . . ,

 If N is a Poisson random variable, it can be shown that E(N) = var

N = λ.

 Define Nt to be the number of arrivals to occur during any

time interval of length t.

 Nt is Poisson with parameter λt, E(Nt) = var Nt = λt.

 An average of λt arrivals occur during a time interval of

length t, so λ may be thought of as the average number of arrivals per unit time, or the arrival rate.

1.

2.

Arrivals defined on nonoverlapping time intervals are independent (for example, the number of arrivals occurring between times 1 and 10 does not give us any information about the number of arrivals occurring between times 30 and 50). For small t (and any value of t), the probability of one arrival occurring between times t and t +∆t is λ∆t + o(t), where o(t) refers to any quantity satisfying

If the arrival rate is stationary, if bulk arrivals cannot occur, and if past arrivals do not affect future arrivals, Then interarrival times will follow an exponential distribution

with parameter λ, and the number of arrivals in any interval of length t is Poisson with parameter λt.

Example 1: Beer Orders  The number of glasses of beer ordered per hour at Dick’s

Pub follows a Poisson distribution, with an average of 30 beers per hour being ordered. 1. 2. 3.

Find the probability that exactly 60 beers are ordered between 10 P.M. and 12 midnight. Find the mean and standard deviation of the number of beers ordered between 9 P.M. and 1 A.M. Find the probability that the time between two consecutive orders is between 1 and 3 minutes.

1.

The number of beers ordered between 10 P.M. and 12 midnight will follow a Poisson distribution with parameter 2(30) = 60. e −60 6060 P( N t = 60) = = 0.051 60!

2.

λ = 30, t = 4  E(Nt) = λt = 30 (4) = 120 Std.Dev (Nt) = 120 = 10.95

3.

Let X be the time (in minutes) between successive beer orders The mean number of orders per minute is exponential with parameter or rate 30/60 = 0.5 beer per minute.

Erlang distribution  If interarrival times do not appear to be exponential, they are

often modeled by an Erlang distribution.

 Rate parameter = R  Shape parameter = k

 For k = 1, the Erlang distribution is an exponential distribution

with parameter R.  As k increases, the Erlang distribution behaves more and more like a normal distribution. For extremely large values of k, it approaches a random variable with zero variance (constant interarrival time).  The Erlang distribution has the same distribution as the random variable A1 + A2 +...+ Ak, where each Ai is an exponential random variable with parameter k λ, and the Ai’s are independent random variables.  The interarrival process is equivalent to a customer going through k phases (each of which has the no-memory property) before arriving. The shape parameter is often referred to as the number of phases of the Erlang distribution.

Modeling the service process  Assume that the service times of different customers are independent

random variables and that each customer’s service time is governed by a random variable S having a density function s(t).

1

= mean service time for customer (hours per customer)

µ µ = service rate (customers per hour)

 Service times can be accurately modeled as exponential random

variables.

 What is the probability that the customer who is waiting will be the last of

the four customers to complete service?  One of customers 1–3 (say, customer 3) will be the first to complete service. Then customer 4 will enter service.  By the no-memory property, customer 4’s service time has the same distribution as the remaining service times of customers 1 and 2 = 1/3.

 The actual service time may be incosistent with the no

memory property  Erlang distribution can be closely fitted to observed service times.

 In certain situations, interarrival or service times may be

modeled as having zero variance; in this case, interarrival or service times are considered to be deterministic.

The Kendall-Lee Notation for Queuing Systems  Each queuing system is described by six characteristics:

1/2/3/4/5/6 1.

The nature of the arrival process M = Interarrival times are independent, identically distributed (iid) random variables having an exponential distribution. D = Interarrival times are iid and deterministic. Ek = Interarrival times are iid Erlangs with shape parameter k. GI = Interarrival times are iid and governed by some general distribution

2.

The nature of the service process M = Service times are iid and exponentially distributed. D = Service times are iid and deterministic. Ek = Service times are iid Erlangs with shape parameter k. G = Service times are iid and follow some general distribution.

The number of parallel servers 4. The queue discipline 3.

FCFS First come, first served LCFS Last come, first served SIRO Service in random order GD General queue discipline

5.

6.

The maximum allowable number of customers in the system (including customers who are waiting and customers who are in service). The size of the population from which customers are drawn.

In many important models 4/5/6 is GD/∞/∞. If this is the case, then 4/5/6 is often omitted. Example: M/E2/8/FCFS/10/∞ Represents: A health clinic with 8 doctors, exponential interarrival times, two-phase Erlang service times, an FCFS queue discipline, and a total capacity of 10 patients

Waiting time paradox  On the average, somebody who arrives at a random time should arrive in the

middle of a typical interval between arrivals of successive buses. If we arrive at the midpoint of a typical interval, and the average time between buses is 60 minutes, then we should have to wait, on the average, (1/2)60 = 30 minutes for the next bus  INCORRECT

 If A is the random variable for the time between buses, then the average time

until the next bus (as seen by an arrival who is equally likely to come at any time) is given by 1 3600  =  60 +  = 60 2 60 

Problems: Group A Suppose I arrive at an M/M/7/FCFS/8/∞ queuing system when all servers are busy. What is the probability that I will complete service before at least one of the seven customers in service? 2. The time between buses follows the mass function shownin Table 2. What is the average length of time one must wait for a bus? 1.

The time between arrivals of buses follows an exponential distribution, with a mean of 60 minutes.

4. a. b. c. d.

What is the probability that exactly four buses will arrive during the next 2 hours? That at least two buses will arrive during the next 2 hours? That no buses will arrive during the next 2 hours? A bus has just arrived. What is the probability that it will be between 30 and 90 minutes before the next bus arrives?

Birth-Death processes

Birth-Death Process  A birth–death process is a continuous-time stochastic

process for which the system’s state at any time is a nonnegative integer.  Laws of motion for birth-death process 1.

2.

3.

With probability λj∆t + o(∆t), a birth occurs between time t and time t + ∆t. A birth increases the system state by 1, to j + 1. With probability µjt + o(∆t), a death occurs between time t and time t + ∆ t. A death decreases the system state by 1, to j-1. Note that µ0 = 0 must hold, or a negative state could occur. Births and deaths are independent of each other.

 Any birth–death process is completely specified by

knowledge of the birth rates λj and the death rates µj

 The no-memory property of the exponential distribution ->

Probability that a customer will complete service between t and t + ∆t is given by

 For j>=1, µj = µ  If we assume that service completions and arrivals occur

independently, then an M/M/1/FCFS/∞/∞ queuing system is a birth–death process.

 Consider an M/M/3/FCFS/∞/∞ queuing system in which

interarrival times are exponential with λ= 4 and service times are exponential with µ = 5

A birth-death process

 If either interarrival times or service times are

nonexponential, then the birth–death process model is not appropriate.  A modified birth–death model can be developed if service times and interarrival times are Erlang distributions.

Derivation of steady state probabilities for birth-death process  Note that there are four ways for the state at time t +∆t to be

j.

 the probability that the state of the system will be j - 1 at

time t and j at time t +∆ t

 Thus:

 Regrouping

o(∆t )

=

 Dividing both sides by ∆t and letting ∆t approaches zero

 Steady state: π = lim Pij (t ) t →∞

 Thus, for j>=1

 And for j=0

P'ij (t ) = 0

 At any time t that we observe a birth–death process, it must be true

that for each state j, the number of times we have entered state j differs by at most 1 from the number of times we have left state j.  Thus, for large t: Unit time Unit time

 For j>=1 Unit time

Unit time

Thus for j>=1

 Thus for j>=1

Flow balance equations Conservation of flow equation

Solution of birth-death flow balance equations  Begin by expressing all πj’s in terms of π0

 Define:

 Then:

 And

 Hence:

 If

∑

j =∞ j =1

c j finite

 If not finite no steady state (arrival rate is at least as large as the

maximum rate at which customers can be served.

Example 2: Indiana Bell  Indiana Bell customer service representatives receive an

average of 1,700 calls per hour.The time between calls follows an exponential distribution. A customer service representative can handle an average of 30 calls per hour. The time required to handle a call is also exponentially distributed. Indiana Bell can put up to 25 people on hold. If 25 people are on hold, a call is lost to the system. Indiana Bell has 75 service representatives. What fraction of the time are all operators busy? 2. What fraction of all calls are lost to the system? 1.

π75 + π76 +...+ π100 = 0.013 2. π100 = 0.0000028 1.

M/M/1/GD/∞/∞ queuing system and queuing optimization model

The M/M/1/GD/∞/ ∞ Queuing System  An M/M/1/GD/∞/ ∞ queuing system can be modeled as

death birth process with parameters:

 Use equation (15) – (19)

 Define: ρ=λ/µ  Substituting (21) into (17)

 Define S = (1+ρ+ ρ2+ ρ3...)

ρS = ρ+ ρ2+ ρ3... S- ρS = 1

 Thus

 If ρ>=1 then the system will blow up.

Derivation of L  The average number of customers present in the queuing

system (L) is given by:

Defining:

 Now

Derivation of Lq  The expected number of people waiting in line (Lq)  If j people are present the system, there will be j-1 people

present in the line.

 Since L = ρ/(1- ρ)

Derivation of Ls  The expected number of customers in server (Ls)

 We could have determined Lq from:

The queuing formula L = λW  Little’s queuing formula, define:

 All averages are in the steady state:

 For the M/M/1/GD/∞/ ∞ queuing system

Example 3: Drive in banking  An average of 10 cars per hour arrive at a single-server drive-in

teller. Assume that the average service time for each customer is 4 minutes, and both interarrival times and service times are exponential. Answer the following questions: 1. 2. 3. 4.

What is the probability that the teller is idle? What is the average number of cars waiting in line for the teller? (A car that is being served is not considered to be waiting in line.) What is the average amount of time a drive-in customer spends in the bank parking lot (including time in service)? On the average, how many customers per hour will be served by the teller?

π0 = 1 - ρ = 1 – 2/3 = 1/3 2. We seek Lq: 1.

3.

We seek L: 1 - 2/3

Thus W = 2/10 =1/5 hour = 12 minutes.

4.

If the teller were always busy then µ = 15. The teller is only busy 2/3rd of the time, thus he will serve an average of 2/3(15) = 10 customers.

Example 4: Service station  Suppose that all car owners fill up when their tanks are

exactly half full. At the present time, an average of 7.5 customers per hour arrive at a single-pump gas station. It takes an average of 4 minutes to service a car. Assume that interarrival times and service times are both exponential.  Compute L and W!  We have an M/M/1/GD/∞/ ∞ system λ = 7.5 cars per hr

and µ = 15 cars/hr  ρ = 0.50  L = 0.5/(1-0.5) = 1 and W = L/ λ = 1/7.5 = 0.13 hr.

 Suppose that a gas shortage occurs and panic buying takes

place. To model this phenomenon, suppose that all car owners now purchase gas when their tanks are exactly threequarters full. Since each car owner is now putting less gas into the tank during each visit to the station, we assume that the average service time has been reduced to 3 1/3 minutes. How has panic buying affected L andW ?  Now λ = 2(7.5) = 15 cars/hr (Each owner will fill up twice as

often). µ = 60/3.333 = 18 cars/hr  ρ = 5/6 1- 5/6

 As ρ approaches 1, L and W increase rapidly

A queuing optimization model

Example 5: Tool Center  Machinists who work at a tool-and-die plant must check out tools

from a tool center. An average of ten machinists per hour arrive seeking tools. At present, the tool center is staffed by a clerk who is paid $6 per hour and who takes an average of 5 minutes to handle each request for tools. Since each machinist produces $10 worth of goods per hour, each hour that a machinist spends at the tool center costs the company $10. The company is deciding whether or not it is worthwhile to hire (at $4 per hour) a helper for the clerk. If the helper is hired, the clerk will take an average of only 4 minutes to process requestsfor tools. Assume that service and interarrival times are exponential. Should the helper be hired?

 The firms wants to

hour

hour

Customer

Customer

customer

hour

Machine-hr

hr

 If the helper is not hired: λ = 10 machinists per hr, and µ =

12 machinist per hr W = 1/(12-10) = ½ hr. hour

Expected cost per hr = 6 + 50 = $56  With the helper: µ = 15 W = 1/(15-10) = 1/5 hour

Expected cost per hr = (6+4) + 20 = $30

Should hire the helper

 The queuing formula L = λW is very general and can be

applied to many situations that do not seem to be queuing problems. Think of any situation where a quantity (such as mortgage loan applications, potatoes at McDonald’s, revenues from computer sales) flows through a system.

Note: Examples 6 and 7 are not discussed

Problems: Group A A fast-food restaurant has one drive-through window. An average of 40 customers per hour arrive at the window. It takes an average of 1 minute to serve a customer. Assume that interarrival and service times are exponential.

4.

a) b)

c)

On the average, how many customers are waiting in line? On the average, how long does a customer spend at the restaurant (from time of arrival to time service is completed)? What fraction of the time are more than 3 cars waiting for service (this includes the car (if any) at the window)?

M/M/1/GD/c/∞ queuing system

 Total capacity = c

 Parameters

 Define ρ = λ/µ, using Eq. 16 – 19 the steady state is then

given by

 When λ ≠ µ

 If λ = µ, all cj’s = 1, and all πj’s equal

 Thus:

The actual arrival

 Even when λ ≥ µ, the system will never blow up.

Example 8: Barber shop  A one-man barber shop has a total of 10 seats. Interarrival

times are exponentially distributed, and an average of 20 prospective customers arrive each hour at the shop. Those customers who find the shop full do not enter. The barber takes an average of 12 minutes to cut each customer’s hair. Haircut times are exponentially distributed. On the average, how many haircuts per hour will the barber complete? 2. On the average, how much time will be spent in the shop by a customer who enters? 1.

1.

π10 will leave the shop. An average of λ(1- π10 ) will actually enters the shop.

c = 10, λ = 20, µ = 5 ρ = 20/5 = 4

Thus an average of 20 (1-0.75) = 5 customers per hour will receive haircuts.  or (20 -5 =15) customers per hour will leave the shop.

2.

To determine W,

20 (1-0.75)

 A service facility consists of one server who can serve an

average of 2 customers per hour (service times are exponential). An average of 3 customers per hour arrive at the facility (interarrival times are assumed exponential).The system capacity is 3 customers. On the average, how many potential customers enter the system each hour? b. What is the probability that the server will be busy? a.

The M/M/s/GD/∞/∞ queuing system

 Assume that interarrival times are exponential (with rate λ),

service times are exponential (with rate µ), and there is a single line of customers waiting to be served at one of s parallel servers.  If j servers are occupied then service rate:

 With parameters:

 Define: ρ=λ/sµ yields the steady state probabilities:

 If λ≥1 then no steady state exists.

 The steady state probability that all servers are busy:

 It can be shown that:

in queue

in the system

Example 9: Bank Tellers  Consider a bank with two tellers. An average of 80 customers

per hour arrive at the bank and wait in a single line for an idle teller. The average time it takes to serve a customer is 1.2 minutes. Assume that interarrival times and service times are exponential. Determine The expected number of customers present in the bank 2. The expected length of time a customer spends in the bank 3. The fraction of time that a particular teller is idle 1.

1.

The system: M/M/2/GD/ ∞/ ∞ λ = 80, µ = 50, ρ = 80/2(5) = 0.8