1 - fondamenti di teoria delle code - univpm.it · ⇒f dimensione della sorgente che genera le...

Fondamenti di teoria delle code

1

Teoria delle code

Aspetti fondamentali


2

Lo scopo dell’analisiAndamento del costo di un sistema a coda

Efficienza del servizio

Costo totale

Costo del servizio reso

Costo totale

Costo del servizio reso

Costo dell'attesa


3

Elementi caratteristici di un sistema a coda

Sorgente delle richieste di servizio

Punto di erogazione del servizioArrivi al

sistema

Sistema

Uscita dal sistema

Coda


4

Tipologie di un sistema a codaCanale singolo, fase singola

Canale singolo, fase multipla

Canale multiplo, fase singola

Canale multiplo, fase multipla


5

Le distribuzioni degli arrivi e dei servizi

Arrivi giorno 1 (27)



0 1 2 3 4 5 6 7 8 9 10

0 0,5 1 0 0,5 1 0 0,5 1


6

Distribuzione esponenziale negativa

0

0,5

1

1,5

2

2,5

3

3,5

0 1 2 3 4 5 60

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

Distribuzioneesponenziale negativa(PDF)Distribuzioneesponenziale negativa(CDF)

22 1)(

1)(

1)()(

λσλ

λλ

λ

=

=

−=

⋅=⋅−

⋅−

t

tE

etFetf

t

t

Distribuzione di Poisson

0

0,05

0,1

0,15

0,2

0,25

0 2 4 6 8 10 12 14 16 18 20

0

0,2

0,4

0,6

0,8

1

1,2

Distribuzione diPoisson (PDF)Distribuzione diPoisson (CDF)

tntnE

nettp

tn

n

⋅=

⋅=

⋅⋅=

⋅−

λσ

λ

λ λ

)()(

!)()(

2


7

Le misure di prestazione1. Il numero medio di clienti in attesa, in coda o nel sistema2. Il tempo medio di attesa del cliente, in coda o nel sistema3. Il tasso di utilizzo del sistema, riferito alla percentuale di capacità

utilizzata4. Il costo complessivo di gestione del sistema, legato alla

efficienza del servizio reso5. La probabilità che un cliente in arrivo nel sistema debba

attendere prima di ricevere il servizio richiesto

Le discipline di gestione1. FIFO (First In First Out)2. LIFO (Last In First Out)3. SIRO (Service In Random Order)4. Gestite in base alla priorità dei clienti


8

μλ=r2. Il numero medio di presenze nel sistema

rLpnL qn ns +=⋅= ∑∞

=0

3. Il numero medio di presenze in coda

∑∞

=⋅−=

cn nq pcnL )(4. Il tempo medio di permanenza in coda

λqq LW =

5. Il tempo medio di permanenza nel sistema

μλ 1+== qss WLW

6. Il tasso di utilizzo del sistema

)( μλρ ⋅= c

CLASSIFICAZIONE DI UN SISTEMA A CODA

( ) ( )fedcba //://

⇒a distribuzione dei tempi di arrivo⇒b distribuzione dei tempi di servizio⇒c numero di canali del sistema⇒d disciplina della coda⇒e numero massimo di presenze nel sistema⇒f dimensione della sorgente che genera le richieste di servizio

1. il numero medio di clienti serviti

LE RELAZIONIFONDAMENTALI


9

Sistemi a coda monocanale (M/M/1):(GD/∞/∞)

)1(

)1(1

1

1

)1(1

2

ρμρ

λρμλ

ρρ

ρρ

ρρ

ρμλρ

−⋅==

−⋅==

−=

−=

−⋅=

<⇔=

qq

ss

qs

nn

LWLW

LL

pseastazionaricondizione

Sistemi a coda monocanale (G/M/1):(GD/∞/∞)

0

0

0

00

11

1

)1(0

ppWW

ep

ppp

qs

p

nn

⋅−

=+=

=−

−⋅=⋅

−

μμ

λμLe espressioni riportate sono valide per

tempo tra due arrivi consecutivi costante


10

Sistemi a coda monocanale (M/G/1):(GD/∞/∞)

λλ

ρρρσλ

ρρμλρ

ss

qq

qsq

LWL

W

LLL

pseastazionaricondizione

==

+=−⋅+⋅

=

−=<⇔=

)1(2

11

2220

Le espressioni sono valide per distribuzioni dei tempi di servizio di qualsiasi

natura, caratterizzate da valor medio e da varianza μ1 2σ


11

Sistemi a coda multicanale (M/M/C):(GD/∞/∞)

⎩⎨⎧

≥⇒⋅<⇒⋅

=cnccnn

c μμ

μ

le equazioni che definiscono il modello sono:

( )

11

00

0

0

1!!

!

0!

1

−−

=

−

⎥⎦

⎤⎢⎣

⎡−⋅

+=

⎪⎪⎩

⎪⎪⎨

⎧

>⇒⋅⋅

≤≤⇒⋅=

<⇔=

∑c

n

cn

cn

n

n

n

crcr

nrp

cnpcc

r

cnpnr

p

crseastazionaricondizioner μλ

si ricava( )

)1(!

)(!1

0

02

crcprp

pcc

rL

cw

c

q

−⋅⋅=

⋅−⋅⋅−

⋅⋅=

λμμλ

Il modello è caratterizzato da un tasso di servizio variabile in funzione delle presenze n all’interno del sistema:


12

0,0330,60020,50

0,5000,50010,50

0,0330,60020,50

0,3680,55010,45

0,0240,63320,45

0,3680,55010,45

0,0170,66720,40

0,2670,60010,40

0,0110,70220,35

0,1880,65010,35

0,0070,73920,30

0,1290,70010,30

0,0040,77820,25

0,0830,75010,25

0,0020,81820,20

0,0500,80010,20

0,0010,86020,15

0,0260,85010,15

LqP0cλ/μ

0,0240,42530,85

0,1870,40420,85

4,8170,15010,85

0,0190,44730,80

0,1520,42920,80

3,2000,20010,80

0,0150,47130,75

0,1230,45520,75

2,2500,25010,75

0,0110,49530,70

0,0980,48120,70

1,6330,30010,70

0,0080,52130,65

0,0770,50920,65

1,2070,35010,65

0,0060,54830,60

0,0590,53820,60

0,9000,40010,60

LqP0cλ/μ

0,0160,30041,20

0,0940,29431,20

0,6750,25021,20

0,0660,32731,10

0,4770,29021,10

0,0020,33351,10

0,0070,36741,00

0,0450,36431,00

0,3330,33321,00

0,0050,38640,95

0,0370,38330,95

0,2770,35620,95

18,0500,05010,95

0,0040,40640,90

0,0300,40330,90

0,2290,37920,90

8,1000,10010,90

0,0030,42740,85

LqP0cλ/μ


13

4,4260,08121,70

0,0120,20151,60

0,0600,19941,60

0,3130,18731,60

2,8440,11121,60

0,0090,22351,50

0,0450,22141,50

0,2370,21131,50

1,9290,14321,50

0,0060,24651,40

0,0320,24541,40

0,1770,23631,40

1,3450,17621,40

0,0040,27251,30

0,0230,27141,30

0,1300,26431,30

0,9510,21221,30

0,0030,30151,20

LqP0cλ/μ

0,2200,11742,10

1,1490,09632,10

0,0090,13562,00

0,0400,13452,00

0,1740,13042,00

0,8890,11132,00

0,0070,14961,90

0,0300,14951,90

0,1360,14541,90

0,6880,12831,90

17,5870,02621,90

0,0230,16551,80

0,1050,16241,80

0,5320,14631,80

7,6740,05321,80

0,0170,18251,70

0,0800,18041,70

0,4090,16631,70

LqP0cλ/μ

0,1300,08052,50

0,5330,07442,50

3,5110,04532,50

0,0070,09172,40

0,0270,09062,40

0,1050,08952,40

0,4310,08342,40

2,5890,05632,40

0,0210,10062,30

0,0840,09952,30

0,3460,09342,30

1,9510,06832,30

0,0160,11162,20

0,0660,10952,20

0,2770,10542,20

1,4910,08132,20

0,0120,12262,10

0,0520,12152,10

LqP0cλ/μ


14

27,1930,00832,90

0,0180,06172,80

0,0660,06062,80

0,2410,05852,80

1,0000,05042,80

12,2730,01632,80

0,0140,06772,70

0,0530,06762,70

0,1980,06552,70

0,8110,05742,70

7,3540,02532,70

0,0110,07472,60

0,0430,07462,60

0,1610,07252,60

0,6580,06542,60

4,9330,03532,60

0,0090,08272,50

0,0340,08262,50

LqP0cλ/μ

0,0430,04073,20

0,1450,04063,20

0,5130,03753,20

2,3860,02743,20

0,0100,04583,10

0,0350,04573,10

0,1200,04463,10

0,4270,04253,10

1,9020,03243,10

0,0080,05083,00

0,0280,05073,00

0,0990,04963,00

0,3540,04753,00

1,5280,03843,00

0,0230,05572,90

0,0810,05462,90

0,2930,05252,90

1,2340,04442,90

LqP0cλ/μ

7,0900,01143,60

0,0070,03093,50

0,0230,03083,50

0,0760,03073,50

0,2480,02963,50

0,8820,02653,50

5,1650,01543,50

0,0190,03383,40

0,0630,03373,40

0,2090,03263,40

0,7370,02953,40

3,9060,01943,40

0,0150,03783,30

0,0520,03773,30

0,1740,03663,30

0,6150,03353,30

3,0270,02343,30

0,0120,04183,20

LqP0cλ/μ


15

36,8590,00243,90

0,0130,02293,80

0,0410,02283,80

0,1290,02273,80

0,4120,02163,80

1,5190,01753,80

16,9370,00543,80

0,0100,02593,70

0,0340,02583,70

0,1090,02473,70

0,3490,02363,70

1,2650,02053,70

10,3470,00843,70

0,0080,02793,60

0,0280,02783,60

0,0910,02773,60

0,2950,02663,60

1,0550,02353,60

LqP0cλ/μ

0,2480,01474,20

0,7840,01364,20

3,3270,00954,20

0,0230,01794,10

0,0700,01684,10

0,2120,01674,10

0,6680,01564,10

2,7030,01154,10

0,0190,01894,00

0,0590,01884,00

0,1800,01874,00

0,5700,01764,00

2,2160,01354,00

0,0160,02093,90

0,0500,02083,90

0,1530,02073,90

0,4850,01963,90

1,8300,01553,90

LqP0cλ/μ

0,3910,01074,50

1,2650,00964,50

6,8620,00554,50

0,0130,012104,40

0,0390,01294,40

0,1140,01284,40

0,3370,01274,40

1,0780,01064,40

5,2680,00654,40

0,0110,014104,30

0,0330,01494,30

0,0970,01384,30

0,2890,01374,30

0,9190,01264,30

4,1490,00854,30

0,0090,015104,20

0,0270,01594,20

0,0830,01584,20

LqP0cλ/μ


16

0,6070,00874,80

2,0710,00664,80

21,6410,00254,80

0,0220,009104,70

0,0640,00994,70

0,1810,00984,70

0,5250,00874,70

1,7520,00764,70

13,3820,00354,70

0,0180,010104,60

0,0540,01094,60

0,1560,01084,60

0,4530,00974,60

1,4870,00864,60

9,2890,00454,60

0,0150,011104,50

0,0460,01194,50

0,1340,01184,50

LqP0cλ/μ

0,9360,00575,10

3,5360,00465,10

0,0130,007115,00

0,0360,007105,00

0,1010,00795,00

0,2790,00685,00

0,8100,00675,00

2,9380,00565,00

0,0110,007114,90

0,0310,007104,90

0,0870,00794,90

0,2420,00784,90

0,7020,00774,90

2,4590,00564,90

46,5660,00154,90

0,0260,008104,80

0,0740,00894,80

0,2090,00884,80

LqP0cλ/μ

6,6610,00265,40

0,0070,005125,30

0,0210,005115,30

0,0570,005105,30

0,1550,00595,30

0,4220,00585,30

1,2490,00475,30

5,3030,00365,30

0,0180,006115,20

0,0490,005105,20

0,1350,00595,20

0,3680,00585,20

1,0810,00575,20

4,3010,00365,20

0,0150,006115,10

0,0420,006105,10

0,1170,00695,10

0,3210,00685,10

LqP0cλ/μ


17

0,0880,004105,60

0,2330,00495,60

0,6310,00385,60

1,9440,00375,60

11,5190,00165,60

0,0100,004125,50

0,0280,004115,50

0,0770,004105,50

0,2040,00495,50

0,5530,00485,50

1,6740,00375,50

8,5900,00265,50

0,0090,005125,40

0,0240,005115,40

0,0660,004105,40

0,1780,00495,40

0,4830,00485,40

1,4440,00475,40

LqP0cλ/μ

3,1130,00275,90

56,3000,00065,90

0,0170,003125,80

0,0440,003115,80

0,1160,003105,80

0,3030,00395,80

0,8230,00385,80

2,6480,00275,80

26,3730,00165,80

0,0140,003125,70

0,0380,003115,70

0,1020,003105,70

0,2660,00395,70

0,7210,00385,70

2,2640,00275,70

16,4460,00165,70

0,0120,004125,60

0,0330,004115,60

LqP0cλ/μ

0,0080,002136,00

0,0220,002126,00

0,0590,002116,00

0,1520,002106,00

0,3920,00296,00

1,0710,00286,00

3,6830,00276,00

0,0510,003115,90

0,1330,003105,90

0,3450,00395,90

0,9390,00285,90

LqP0cλ/μ


18

Sistemi a coda: modello del manutentore (M/M/R):(GD/K/K)

KnRpnKpR

RnpnKpn

ppK

nn

nn

o

<≤⋅⋅−=⋅⋅

<≤⋅⋅−=⋅⋅+

⋅=⋅⋅

+

+

)(

1 )()1(

1

1

1

λμ

λμ

μλ

essendo

∑∑ ==

−

−

⋅−=⇒−=

⋅=⇒⋅=

⋅=

K

n nK

n n

nnn

n

nn

kpppp

pkppp

pp

pp

Kpp

10010

00

1

10

0

1

11

μλ

si ricava

λ

λ

λλ

ssqs

K

Rnq

qnq

R

nns

LWRRLL

LWpRnL

pRnRLK

=−+=

=⋅−=

⋅−=−⋅=

∑

∑

+=

=

)(

)(

)( )(

1

0

Le equazioni che regolano il comportamento del modello sono:


19

R = 4 K = 20 λ = 10 μ= 20 ρ = 0,50 λ1 = 80n pn+1 / pn pn+1 / p0 pn (n-R) pn (R-n) pn

0 10 10 0,00001 5,96574E-051 4,75 47,5 0,00015 0,0004474312 3 142,5 0,00071 0,0014168633 2,125 302,8125 0,00213 0,0021252954 2 605,625 0,00452 0 05 1,875 1135,546875 0,00903 0,0090325056 1,75 1987,207031 0,01694 0,0338718927 1,625 3229,211426 0,02964 0,0889137168 1,5 4843,817139 0,04816 0,1926463859 1,375 6660,248566 0,07224 0,361211972

10 1,25 8325,310707 0,09933 0,59599975411 1,125 9365,974545 0,12417 0,86916630912 1 9365,974545 0,13969 1,1174995413 0,875 8195,227727 0,13969 1,25718698214 0,75 6146,420795 0,12223 1,22226512115 0,625 3841,512997 0,09167 1,00836872516 0,5 1920,756499 0,05729 0,68752413117 0,375 720,283687 0,02865 0,37240890418 0,25 180,0709217 0,01074 0,15039590419 0,125 22,50886522 0,00269 0,04028461720 0 0 0,00034 0,005371282

somma Kn = 67048,51 somma pn = 1,00 Lq = 8,012 Rmedio = 0,004 Ls = 12,008Wq = 0,100 Ws = 0,150

Esercizio modello (M/M/4):(GD/20/20)


20

R = 6 K = 20 λ = 10 μ= 20 ρ = 0,50 λ1 = 114n pn+1 / pn pn+1 / p0 pn (n-R) pn (R-n) pn

0 10 10 0,00016 0,0009747661 4,75 47,5 0,00162 0,0081230472 3 142,5 0,00772 0,0308675783 2,125 302,8125 0,02315 0,069452054 1,6 484,5 0,04920 0,0983904045 1,25 605,625 0,07871 0,0787123236 1,166666667 706,5625 0,09839 0 07 1,083333333 765,4427083 0,11479 0,1147888058 1 765,4427083 0,12435 0,2487090779 0,916666667 701,655816 0,12435 0,373063616

10 0,833333333 584,71318 0,11399 0,45596664111 0,75 438,534885 0,09499 0,47496525112 0,666666667 292,35659 0,07124 0,42746872613 0,583333333 170,5413442 0,04750 0,33247567614 0,5 85,27067208 0,02771 0,22165045115 0,416666667 35,5294467 0,01385 0,12467837816 0,333333333 11,8431489 0,00577 0,05772147217 0,25 2,960787225 0,00192 0,0211645418 0,166666667 0,493464537 0,00048 0,00577214719 0,083333333 0,041122045 0,00008 0,00104219320 0 0 0,00001 9,35302E-05

somma Kn = 6154,33 somma pn = 1,00 Lq = 2,860 Rmedio = 0,287 Ls = 8,573Wq = 0,025 Ws = 0,075

Esercizio modello (M/M/6):(GD/20/20)


21

Sistemi a coda con priorità differente dei clienti

∑

∑

= ⋅−=

=

⋅−=

=

⋅=

k

ll

k

q

l l

cB

BL

A

c

1

0

1

1

1

μλ

ρλ

λλμλρ

)(

)(

si ricava

kqkkq

kqks

kkkq

WL

WW

BBAW

,,

,,

,

⋅=

+=

⋅⋅=

−

λμ1

1

1

Per l’analisi di questa classe di modelli si utilizzano dei parametri intermedi definiti da:


22

Sistemi a coda con priorità differente dei clienti: esempio numerico

• Un centro di lavoro composto da sei macchine gestisce la riparazione di utensili operanti su altri sistemi di fabbricazione.

• All’arrivo dell’utensile al centro di lavoro gli si assegna una priorità in base al gradi di urgenza della riparazione richiesta.

• Le richieste di riparazione sono caratterizzate da tempi di arrivo con distribuzione esponenziale negativa con tassi medi di arrivo– λ1= 2 arrivi/ora– λ2= 2 arrivi/ora– λ3= 1 arrivi/ora

• Il tasso di servizio delle macchine che effettuano la riparazione degli utensili è pari a– µ= 1 riparazioni/ora


23

Sistemi a coda con priorità differente dei clienti: esempio numerico

Il tasso di arrivo complessivo è ∑ ++== 122kλλ

Il tasso di utilizzo è 833061

5 ,=⋅

=⋅

=μ

λρc

Con i valori λ=5 µ=1 e c=6 dalle tabelle delle code multicanale di ottiene Lq=2,938 ⇒ A=10,19

765,1765,11167,01

884,0442,01333,01

294,0147,01667,01

1

3,33,32

3,321

3

2,22,21

2,21

2

1,11,10

1,1

1

0

=⋅==⋅⋅

==⋅

++−=

=⋅==⋅⋅

==⋅+

−=

=⋅==⋅⋅

==⋅

−=

=

qqq

qqq

qqq

WLBBA

Wc

B

WLBBA

Wc

B

WLBBA

Wc

B

B

λμ

λλλ

λμλλ

λμ

λ


24

Determinazione del livello di servizio ottimo

[ ]μΔ⋅

=h

c €1

c2: costo unitario dell’attesa del cliente

[ ]lunghezzah

c⋅

=€

2

μμμ

μ

μμμ

ddLccTC

dd

LccTC

s

s

)()(

)()(

⋅+=

⋅+⋅=

21

21

per la coda (M/M/1)

1

2221 c

cccTCddLs λλμ

λμλμ

μλμλ ⋅

+=⇒−

⋅−=⇒−

=)(

)(

Ipotesi: si consideri una coda a singolo canale con tasso di arrivo λ e tasso di servizio μ . Il tasso si servizio sia controllabile

c1: costo unitario dell’incremento del tasso di servizio


25

Determinazione del numero ottimo di stazioni di servizio

)()()()(

cTCcTCcTCcTC

≥+≥−

11

ovvero quando

)()()()( cLcLcccLcL ssss −−≤≤++ 11

2

1

c1: costo unitario per unità di servizio addizionaleLs(μ ): presenze nel sistema in corrispondenza di c stazioni di servizioEssendo c un valore discreto la condizione di ottimo si verifica per il numero di stazioni c per cui si ha:


26

Determinazione del livello di servizio ottimo: esempio numerico

• Per un sistema a coda sono noti il costo di aggiunta di una stazione di servizio [c1=5] ed il costo unitario relativo alla permanenza nel sistema [c2=8]

• Il sistema è caratterizzato da un tasso di arrivo pari a λ=8 e da un tasso di servizio pari a µ=16

• Si deve valutare se inserire nel sistema un numero di stazioni di servizio pari a1,2 o 3


27

3616170835170167000303264122830825283025003302

131815150501

,,,,,,,,,,

,,

=⋅+⋅=⋅+⋅=⋅+⋅

+=⋅

= CostoLLc

Lstazioninumero qsq ρμ

λρ

Determinazione del livello di servizio ottimo: esempio numerico

1 - fondamenti di teoria delle code - univpm.it · ⇒f dimensione della sorgente che genera le...

Documents

Transcript of 1 - fondamenti di teoria delle code - univpm.it · ⇒f dimensione della sorgente che genera le...