1

Teoria asteptarii

Termeni utilizati Sistem de servire - un sistem in care se executa o anumita activitate sau se efectueaza un anumit serviciu Clienti obiectele asupra carora se executa activitatea sau serviciul respective Statie de servire nu poate deservi decat un singur client in acelasi timp Fir de asteptare clientii care asteapta sau statiile de servire neocupate Disciplina firului de asteptare odinea in care clientii sunt selectati pentru a fi serviti Linie de servire daca serviciul se executa in etape, de catre mai multe statii de servire, secventa acestor statii formeaza o linie de servire Canale de servire mai multe statii sau linii de servire care pot deservi mai multi clienti simultan Ori de cate ori sosirile intr-un sistem de servire sunt astfel incat fie clientii, fie unitatile de servire trebuie sa astepte, avem un proces de asteptare.

2

Intr-un proces de asteptare apare o problema de teoria asteptarii daca:

a) fie intensitatea sosirii clientilor, fie numarul statiilor de servire, fie ambele pot fi controlate

b) exista anumite costuri asociate atat timpului de asteptare al

clientilor cat si statiilor de servire neocupate O problema de teoria asteptarii consta in: planificarea sosirilor sau in stabilizarea numarului statiilor de servire astfel incat sa se minimizeze suma costurilor generate de asteptarea clientilor si de existenta statiilor de servire neocupate. Fire de asteptare circulare clientii serviti care au parasit sistemul pot reintra in multimea clientilor potentiali si revin in firul de asteptare Daca multimea clientilor potentiali este foarte mare, firul circular se comporta ca un fir de asteptare liniar. Starea sistemului un concept fundamental in analiza proceselor de asteptare

- reprezinta o descriere a situatiei actuale care ne permite sa cunoastem in sens probabilistic comportarea viitoare a sistemului

- felul in care sistemul a ajuns in starea respectiva nu are nici o influenta asupra comportarii lui viitoare

Pentru a studia un proces de asteptare trebuie cunoscute legile care guverneaza sosirile si servirile.

3

Exceptand cazul in care sosirile sunt planificate, ipoteza cea mai convenabila dpdv al calculelor consta in a presupune ca sosirile sunt aleatoare (probabilitatea unei sosiri sa fie aceeasi in orice moment de timp). Ipoteza : Probabilitatea sosirii urmatoare nu depinde de momentul sosirii precedente, ci doar de lungimea intervalului de timp intre doua sosiri. Daca h este suficient de mic si daca notam cu intensitatea (rata) sosirilor atunci probabilitatea unei sosiri in intervalul de la t la t+h este h , independent de valoarea lui t.

Sosirile care satisfac aceasta ipoteza se numesc sosiri Poisson probabilitatea ca intr-un interval de timp sa aiba loc n sosiri este

( )!nte nt

Probabilitatea ca intervalul de timp dintre doua sosiri consecutive sa depaseasca o valoare t este aceeasi cu probabilitatea ca o perioada de timp t dupa prima sosire sa nu se mai inregistreze nici o alta sosire. Pentru n=0 aceasta probabilitate este te , deci in ipoteza facuta intervalul de timp dintre doua sosiri consecutive urmeaza o reartitie exponentiala.

4

Exemplu. Un comisvoiajor isi viziteaza lunar clientii si din experienta anterioara s-a constatat ca:

- probabilitatea ca un client sa-i plaseze o comanda este p0 daca clientul a comandat ceva si in luna precedenta

- probabilitatea ca un client sa-i plaseze o comanda este p1 daca nu a comandat ceva in luna precedenta

prima luna

not= 0, a doua luna

not= 1,.......

In fiecare din lunile 1, 2, 3,..... un client se poate afla in una din urmatoarele doua situatii: starea 0 : in luna precedenta nu a plasat nici o comanda starea 1: in luna precedenta aplasat o comanda Daca cunoastem starea clientului in luna 0, p0 si p1 putem determina comportarea sa in viitor. - un probabilitatea ca in luna n clientul sa plaseze o comanda, daca in prima luna nu a plasat nici o comanda comisvoiajorului - vn probabilitatea ca in luna n clientul sa plaseze o comanda, daca in prima luna a plasat o comanda comisvoiajorului Pentru un client care in luna 0 se afla in starea 0 avem ecuatia :

)1(011 nnn upupu +=+ (1) n>0

Pentru un client care in luna 0 se afla in starea 1 avem ecuatia :

)1(011 nnn vpvpv +=+ (2) n>0

01 pu = (3)

5

11 pv = (4)

p0=0,3, p1=0,6

n 1 2 3 4 5 6 7 8 un 0,3 0,39 0,417 0,4251 0,4275 0,4283 0,4285 0,4286vn 0,6 0,48 0,444 0,4330 0,4300 0,4290 0,4287 0,4286

La limita cele doua valori sunt egale Daca exista o valoare v astfel incat pentru n suficient de mare sa avem:

11 ++ ==== nnnn vvuuv atunci v satisface ecuatia:

)1(01 vpvpv += inlocuind valorile obtinem v=0,3/0,7=0,4286 din tabel se observa ca pentru n=8 un si vn iau exact aceasta valoare. v- probabilitatea stationara a plasarii unei comenzi Interpretare a probabilitatilor stationare: dupa o perioada mai lunga de timp, independent de starea initiala a sistemului, probabilitatea plasarii unei comenzi este v (pentru un numar mare de clienti vizitati, proportia comenzilor lunare este v). Observatie: probabilitatile stationare permit estimarea castigurilor si pierderilor pe termen lung.

6

Pentru a vedea cum se obtin parametrii unui sistem de asteptare, consideram consideram un numar foarte mare (N) de sisteme identice. Pentru un sistem care contine n clienti (in curs de servire sau asteptand eliberarea statiilor de servire), notam cu n intensitatea sosirilor si cu n rata servirii.

Daca pn reprezinta probabilitatile stationare ca un sistem sa contina n persoane, atunci vor exista pnN sisteme cu cate n clienti. Deoarece lucram cu probabilitati stationare, numarul sistemelor d n persoane ramane nechimbat, dar sistemele pot fi diferite. Sosirile au loc cu intensitatea n - o sosire transforma un sistem cu n clienti intr-un sistem cu n+1 clienti Rata plecarilor este n , iar o servire transforma un sistem cu n clienti intr-un sistem cu n-1 clienti In fiecare unitate de timp din cele pnN sisteme de n persoane Npnn se transforma in sisteme de n+1 persoane, iar Npnn in sisteme de n-1 persoane. Cum numarul sistemelor de n persoane trebuie sa ramana acelasi, un grup de sisteme care nu contineau n clienti se transforma in sisteme cu n clienti:

NpNpNp nnnnnnn )(1111 +=+ ++

nnnnnnn ppp )(1111 +=+ ++ (5)

0011 pp = (6)

01

01 pp

= (7)

7

01100 = pp (8)

nnnnnnnn pppp = ++ 1111 (9)

021

102 pp

= (10)

nn

nn pp

11

++ =

(11)

021

110

...............

ppn

nn

= (12)

Deoarece sistemul trebuie sa contina un anumit numar de persoane (n=0, sau 1 sau 2, sau 3,....):

1........210 =+++ ppp (13) Din (12) si (13) putem determina p0. Un singur canal cu o intensitate constanta a sosirilor si servirilor (reprezinta cel mai simplu sistem de asteptare)

........21 === , .......21 === In acest caz (12) devine:

00 pppn

n

n

n

== (14) , unde = 1< (15)

8

- intensitatea traficului

1.....2000 =+++ ppp

1........)1( 320 =++++ p cum

=++++

11.......1 32

rezulta

11

0 = p , prin urmare = 10p (16)

Din (14) si (15) rezulta nnp )1( = Numarul mediu de clienti in sistem:

........32 321 +++= pppn Inlocuind valorile obtinute pentru np obtinem:

( )

=

=+++=

=+++=

1)1()1(.......321)1(

......)1(3)1(2)1(

22

32n (17)

Numarul mediu de clienti in firul de asteptare (fara a socoti pe cel in curs de servire):

9

( )

=

=

=+++=

=+++=

11)1(

........)321()1(

.......32

2

2

2

22

432 pppnq

(18)

Numarul mediu de clienti aflati in curs de servire:

qs nnn = =

=

11

2

(19)

Sisteme cu mai multe canale (m canale, pentru fiecare rata servirii fiind ) Daca numarul clientilor prezenti (n) este cel mai mic sau egal cu numarul canalelor (m), n canale vor fi ocupate si rata servirii va fi n . Daca numarul clientilor prezenti este mai mare decat numarul canalelor de servire (m), toate cele m canale sunt ocupate, rata servirii fiind m . Astfel:

=n

++==

=...2,........m1,mn

.m1,2,......n ,,mn

n

Daca m

10

000 !!.......32p

np

np

np

n

n

nn

n

==

= , mn ,........,2,1,0= (20)

( ) 000 !!.......32p

mmp

mmp

mmp mn

n

nmn

n

mn

n

n ===

, (21)

,.......3,2,1 +++= mmmn

Inlocuind valorile lui np din (20) si (21) in (13) obtinem :

1.......!!!)!1(

.....!2 02

2

0

1

00

1

2

2

00 =++++++++

++

pmm

pmm

pm

pm

pppmmmm

mp

mmmp

mp

mmp

mmp

m

mmmmm

/11

!.......))(1(

!.......

!!! 02

002

2

0

1

0

=+++=+++

++

Inlocuind in seria lui 0p obtinem:

)/1(!/)!1/(......!2/11

120 mmmp mm +++++

= (22)

Pentru qnn , si sn obtinem :

2

10

)/1(! mmmpn

m

q

=+

(23)

11

+= qnn (24)

=sn (25)