1 1 Slide

Slide

Queuing or Waiting Line Queuing or Waiting Line ModelsModels

2 2 Slide

Slide

IntroduzioneIntroduzione La Teoria delle Code si propone di

sviluppare modelli per lo studio dei fenomeni d’attesa in presenza di una domanda di un servizio.

Quando la domanda e/o la capacità di erogazione del servizio sono aleatori, si verificano situazioni in cui chi fornisce il servizio non ha la possibilità di soddisfare immediatamente le richieste.

3 3 Slide

Slide

Il Sistema e le ComponentiIl Sistema e le Componenti Un sistema coda è un sistema composto da Un sistema coda è un sistema composto da

servitori, capaci di fornire un servizio, e da servitori, capaci di fornire un servizio, e da clienti da servire.clienti da servire.

I clienti che non trovano un servitore libero I clienti che non trovano un servitore libero al loro arrivo si dispongono in coda in aree al loro arrivo si dispongono in coda in aree di attesa di attesa (buffer)(buffer), e vengono serviti con , e vengono serviti con determinate discipline di servizio.determinate discipline di servizio.

La coda è costituita essenzialmente da due La coda è costituita essenzialmente da due processi stocastici: il processo d'arrivo dei processi stocastici: il processo d'arrivo dei clienti e il processo di servizioclienti e il processo di servizio..

4 4 Slide

Slide

CharacteristicsCharacteristics

Queuing theoryQueuing theory is the study of waiting lines. is the study of waiting lines.

Four characteristics of a queuing system Four characteristics of a queuing system are: are:

• the manner in which customers arrivethe manner in which customers arrive

• the time required for servicethe time required for service

• the priority determining the order of the priority determining the order of serviceservice

• the number and configuration of servers the number and configuration of servers in the system.in the system.

5 5 Slide

Slide

Coda con un Servitore

6 6 Slide

Slide

Coda con On-Off serviceCoda con On-Off serviceCiclo di carico di una nave fino al posizionamento della successiva di C ore, una fase di carico di V ore e una fase per la partenza e il posizionamento della nuova di R ore. Si assume che

• R + V = C;• i veicoli con i container arrivano al tasso

l costante; • gli arrivi in un ciclo C < V dove è il

tasso di carico.

7 7 Slide

Slide

Il CicloIl Ciclo

CR V

n’ n

t

N

L’area grigia è il ritardo totale W

n’ numero di veicoli serviti in un ciclo

n numero di veicoli ritardati

8 8 Slide

Slide

OsservazioniOsservazioniIl numero di veicoli ritardati n = R/(lIl numero di veicoli ritardati n = R/(l -1-1 - m - m-1-1))

n < n’ = lCn < n’ = lC

L’area grigia è W = nR/2 = 1/2lmRL’area grigia è W = nR/2 = 1/2lmR22/(l - m)/(l - m)

Il ritardo medio a regime per veicolo èIl ritardo medio a regime per veicolo è

Il ritardo medio dei veicoli ritardati è R/2.

CλμμR

21

n'W

w2

9 9 Slide

Slide

Single Channel QueueSingle Channel Queue

Server

Waiting line (queue)

Arrivals Departures

Queuing System

10 10 Slide

Slide

Multiple Channel QueueMultiple Channel Queue

Server 1

Waiting line (queue)

Arrivals

Departures

Queuing System

Server 2

Server 3

11 11 Slide

Slide

StructureStructureIn general, the arrival of customers into the In general, the arrival of customers into the system is a system is a random eventrandom event. .

Frequently the arrival pattern is modeled as Frequently the arrival pattern is modeled as a a Poisson processPoisson process..

Service time is also usually a random Service time is also usually a random variable. variable.

A distribution commonly used to describe A distribution commonly used to describe service time is the service time is the exponential distributionexponential distribution..

The most common queue discipline is The most common queue discipline is first first come, first served (FCFS)come, first served (FCFS). .

12 12 Slide

Slide

ClassificationClassificationA A three part codethree part code of the form of the form AA//BB//ss is used to is used to describe various queuing systems. describe various queuing systems.

AA identifies the arrival distribution identifies the arrival distribution

BB the service (departure) distribution the service (departure) distribution

ss the number of servers. the number of servers.

Used symbols are: Used symbols are:

MM Markov distributions (Poisson/exponential) Markov distributions (Poisson/exponential)

DD Deterministic (constant) Deterministic (constant)

GG General distribution (with a known mean, General distribution (with a known mean, variance). variance).

13 13 Slide

Slide

ExampleExample

MM//MM//kk refers to a system in which arrivals refers to a system in which arrivals occur according to a Poisson distribution, occur according to a Poisson distribution, service times follow an exponential service times follow an exponential distribution and there are distribution and there are kk servers servers working at identical service rates.working at identical service rates.

14 14 Slide

Slide

Input CharacteristicsInput Characteristics

l l average arrival average arrival raterate

1/l average 1/l average timetime between arrivals between arrivals

µ µ average service average service raterate for each server for each server

1/1/µ µ average service average service timetime

s s standard deviation of the service timestandard deviation of the service time

15 15 Slide

Slide

Poisson Arrival ProcessPoisson Arrival Process

If the If the average arrival rate is l customers per rate is l customers per time unit, then probability of x arrivals per time unit, then probability of x arrivals per time unit is given by:time unit is given by:

!)(

x

exP

x

16 16 Slide

Slide

ExampleExample

Example: Suppose that customers arrive at Example: Suppose that customers arrive at the rate of l = 8 customers per hour. The the rate of l = 8 customers per hour. The probability that in a given one hour period probability that in a given one hour period there will be exactly six arrivals is:there will be exactly six arrivals is:

1221.0!2

8)6(

82

e

P

17 17 Slide

Slide

Exponential Service TimesExponential Service Times

If the average service time is 1/If the average service time is 1/µ µ time units time units (that is, the average service rate is (that is, the average service rate is µµ customers per time unit), the probability that customers per time unit), the probability that the service time will be less than or equal to the service time will be less than or equal to tt time units is: time units is:

utetP 1)timeservice(

18 18 Slide

Slide

ExampleExample

If the average service time 1/If the average service time 1/µ µ = 6 minute = 6 minute (1/10 hour), then (1/10 hour), then µµ = 10 customers per = 10 customers per hour. The probability that the service time is hour. The probability that the service time is less than or equal 5 minutes (1/12 hours) is:less than or equal 5 minutes (1/12 hours) is:

5654.01)12/1timeservice( 12

110

eP

19 19 Slide

Slide

Operating CharacteristicsOperating Characteristics

PP0 0 = probability the service facility is idle = probability the service facility is idle

LLqq = = average number of units in the average number of units in the

queue awaiting servicequeue awaiting service

LL = = average number of units in the average number of units in the systemsystem

WWqq = average time a unit spends in the = average time a unit spends in the

queue awaiting servicequeue awaiting service

WW = = average time a unit spends in the average time a unit spends in the systemsystem

20 20 Slide

Slide

Analytical FormulasAnalytical Formulas

When the queue discipline is FCFS, When the queue discipline is FCFS, analytical formulas have been derived for analytical formulas have been derived for several different queuing models including several different queuing models including the following: the following: MM//DD/1 /1 MM//MM/1, /1, MM//MM//kk, , MM//GG/1, /1, MM//GG//kk with blocked customers cleared, with blocked customers cleared, and and MM//MM/1 with a finite calling population. /1 with a finite calling population.

Analytical formulas are not available for Analytical formulas are not available for all possible queuing systems. In this all possible queuing systems. In this event, insights may be gained through a event, insights may be gained through a simulation of the system. simulation of the system.

21 21 Slide

Slide

M/D/1 SystemM/D/1 System

qW

qs WW

qs LL

Average number of people or units waiting for service

Average time a person or unit spends in the queue

Average number of people or units in the system

Average time a unit spends in the system

qL

22 22 Slide

Slide

M/M/1 SystemM/M/1 System

1

2

q

qq

q

q

WW

LW

LL

LAverage number of people or units waiting for service

Average time a person or unit spends in the queue

Average number of people or units in the system

Average time a unit spends in the system

23 23 Slide

Slide

M/M/k SystemM/M/k SystemPP0 0 = probability the = probability the

service facility is idleservice facility is idle

Average number of people or units waiting for service

Average time a person or unit spends in the queue

Average number of people or units in the system

Average time a unit spends in the system

1

!1

)/(

)(!

)/(!

)/(

1

02

1

0

0

q

qq

q

k

q

k

n

kn

WW

LW

LL

Pkk

L

kk

kn

P