Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

1

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

B A D A N I A O P E R A C Y J N E

ANALITYCZNE MODELE ELEMENTARNEGO

SYSTEMU OBS

àUGI

M/M/n/r

T

obs

..

.

1

2

1

2

n

T

zg

á

...

r

Materiaáy pomocnicze do wykáadu

[e-mail]

POJ

ĉCIE SYSTEMU M/M/n/

r

W elementarnym systemie obs

áugowym z ograniczoną moĪliwoĞcią oczekiwania zakáada siĊ, Īe

d

áugoĞü kolejki jest ograniczona do

r

miejsc. Je

Īeli w chwili nadejĞcia kolejnego obiektu (zgáoszenia)

do systemu a w kolejce oczekuje ju

Ī

r

obiektów (zg

áoszeĔ), to przychodzący obiekt opuszcza system

bez realizacji obs

áugi. Schemat ideowy otwartego elementarnego systemu obsáugowego z ograniczoną

mo

ĪliwoĞcią oczekiwania obiektów na obsáugĊ, przedstawiono na

rys. 1

. W notacji Kendalla

rozwa

Īany tu system obsáugi ma oznaczenie

M/M/n/r

.

Rys. 1. Schemat ideowy otwartego elementarnego systemu obs

áugowego z ograniczoną moĪliwoĞcią oczekiwania

obiektów na obs

áugĊ (objaĞnienie oznaczeĔ w tekĞcie)

Strumie

Ĕ

zg

áoszeĔ

Poissona

Kolejka

Stanowisko

obs

áugi

Strumie

Ĕ

wyj

Ğciowy

2

r

1

P

O

1

2

n

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

2

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

PRZYK

àADY







Elementarny system naprawczy z ograniczon

ą moĪliwoĞcią oczekiwania obiektów na naprawĊ;

Elementarny system przegl

ądowy z ograniczoną moĪliwoĞcią oczekiwania obiektów na przegląd;

Firma transportowa z ograniczon

ą moĪliwoĞcią oczekiwania zadaĔ transportowych na realizacjĊ.

Strumie

Ĕ

zg

áoszeĔ

Poissona

Kolejka

Stanowisko

obs

áugi

Strumie

Ĕ

wyj

Ğciowy

2

r

1

P

O

1

2

n

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

3

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

ZA

àOĩENIA



Strumie

Ĕ zgáoszeĔ obiektów jest strumieniem Poissona o intensywnoĞci O. Oznacza to m. in., Īe

odst

Ċpy czasu miĊdzy zgáoszeniami opisuje rozkáad wykáadniczy o funkcji gĊstoĞci

prawdopodobie

Ĕstwa

 

t

e

t

f

˜



˜

O

O

;



Stanowisko obs

áugowe ma n takich samych kanaáów obsáugiwania. Czas obsáugi obiektów opisuje

rozk

áad wykáadniczy o funkcji gĊstoĞci prawdopodobieĔstwa

W

P

P

W

˜



˜

e

f

)

(

;



Przed stanowiskiem obiekty mog

ą oczekiwaü w kolejce z ograniczoną do r liczbą miejsc

w kolejce.

Strumie

Ĕ

zg

áoszeĔ

Poissona

Kolejka

Stanowisko

obs

áugi

Strumie

Ĕ

wyj

Ğciowy

2

r

1

P

O

1

2

n

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

4

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

POSZUKIWANE

o

Stany systemu;

o

Graf stanów systemu;

o

Stacjonarne prawdopodobie

Ĕstwa stanów systemu;

o

Prawdopodobie

Ĕstwo odmowy przyjĊcia zgáoszenia do obsáugi w systemie;

o

ĝrednia dáugoĞü kolejki;

o

ĝrednia liczba wolnych kanaáów obsáugi;

o

Wspó

áczynnik przestoju kanaáów obsáugi;

o

Prawdopodobie

Ĕstwo tego, Īe wszystkie kanaáy obsáugi są zajĊte;

o

Inne wybrane charakterystyki systemu.

Strumie

Ĕ

zg

áoszeĔ

Poissona

Kolejka

Stanowisko

obs

áugi

Strumie

Ĕ

wyj

Ğciowy

2

r

1

P

O

1

2

n

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

5

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

ROZWI

ĄZANIA

o

Stany systemu

S

0

 w systemie nie ma zg

áoszeĔ,

S

1

 jedno zg

áoszenie znajduje siĊ w systemie i nastĊpuje jego obsáuga na pierwszym kanale

obs

áugowym, kolejka nie wystĊpuje,

S

2

 dwa zg

áoszenia znajdują siĊ w systemie, pierwsze jest obsáugiwane na pierwszym kanale

obs

áugowym, drugie na drugim kanale obsáugowym,

S

n-1

 (n-1) zg

áoszeĔ znajduje siĊ w systemie, wszystkie obsáugiwane są na kolejnych kanaáach

obs

áugowych; jeden kanaá obsáugowy jest wolny,

S

n

 n zg

áoszeĔ znajduje siĊ w systemie, wszystkie z n kanaáów obsáugowych stanowiska są

zaj

Ċte; kolejka nie wystĊpuje,

S

n+1

 (n+1) zg

áoszeĔ znajduje siĊ w systemie, wszystkie kanaáy obsáugowe są zajĊte, jedno

zg

áoszenie czeka w kolejce,

S

n+r

 (n+r) zg

áoszeĔ znajduje siĊ w systemie, wszystkie kanaáy obsáugowe są zajĊte, r zgáoszeĔ

czeka w kolejce, wszystkie miejsca w kolejce s

ą zajĊte.

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

6

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

o

Graf stanów systemu M/M/n/r

n

P

(n-1)

P

S

n+r

n

P

3

P

. . .

O

O

O

2

P

P

S

0

S

1

S

2

O

O

O

O

n

P

n

P

S

n-1

S

n

S

n+1

. . .

O

STANY

BEZ KOLEJKI

STANY

Z KOLEJK

Ą

Rys. 2. Graf stanów systemu obs

áugowego M/M/n/r (objaĞnienie oznaczeĔ w tekĞcie)

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

7

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

o

Stacjonarne prawdopodobie

Ĕstwa stanów systemu

W celu sformu

áowania zaleĪnoĞci na stacjonarne prawdopodobieĔstwa stanów systemu moĪna

skorzysta

ü z reguáy mnemotechnicznej. Po zastosowaniu reguáy mnemotechnicznej otrzymuje siĊ

nast

Ċpujący ukáad równaĔ zwanych równaniami Chapmana  Koámogorowa:

 

 

  

  

 

  



 

 

 





>

@

 

 

  



 

 

  



 

 

 

 

t

p

n

t

p

t

p

dt

d

r

n

t

p

n

t

p

n

t

p

t

p

dt

d

n

t

p

n

t

p

n

t

p

t

p

dt

d

n

t

p

n

t

p

n

t

p

t

p

dt

d

n

t

p

t

p

t

p

t

p

dt

d

t

p

t

p

t

p

t

p

dt

d

t

p

t

p

t

p

dt

d

r

n

r

n

r

n

n

n

n

n

n

n

n

n

n

n

n

n

























˜



˜



˜



˜





˜



˜



˜





˜

˜



˜







˜



˜



˜





˜

˜



˜





˜

˜



˜



P

O

P

P

O

O

P

P

O

O

P

P

O

O

P

P

O

O

P

P

O

O

P

O

1

2

1

1

1

1

1

2

1

3

2

1

2

2

1

0

1

1

0

0

)

(

.

)

(

.

1

)

(

.

1

)

(

.

1

3

2

)

(

.

2

2

)

(

.

1

)

(

.

0









Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

8

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

Aby uzyska

ü rozwiązanie w stanie ustalonym systemu naleĪy przejĞü do granicy przy tof.

Otrzyma si

Ċ w ten sposób ukáad równaĔ algebraicznych postaci:













>

@









r

n

r

n

n

n

n

n

n

n

n

n

n

p

n

p

.

r

n

p

n

p

n

p

.

n

p

n

p

n

p

.

n

p

n

p

n

p

.

n

p

p

p

.

p

p

p

.

p

p

.



















˜



˜



˜



˜





˜



˜



˜





˜

˜



˜







˜



˜



˜





˜

˜



˜





˜

˜



˜



P

O

P

P

O

O

P

P

O

O

P

P

O

O

P

P

O

O

P

P

O

O

P

O

1

2

1

1

1

1

2

3

2

1

2

1

0

1

0

0

0

1

0

1

0

1

3

2

0

2

2

0

1

0

0









Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

9

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

Po rozwi

ązaniu ukáadu równaĔ algebraicznych otrzymuje siĊ nastĊpujące zaleĪnoĞci na

prawdopodobie

Ĕstwa stacjonarne stanów systemu M/M/n/r:

dla numerów stanów:

n

i

d

d

1



i

i

i

i

p

p

P

O

˜

˜

!

0

a gdy przyjmie si

Ċ, Īe

P

O

U

, to poprzednia zale

ĪnoĞü przyjmuje postaü:

!

0

i

p

p

i

i

U

˜

(4)

W zakresie stanów systemu kiedy nie tworzy si

Ċ w nim jeszcze kolejka zgáoszeĔ (tzw. stany bez

kolejki” – rys. 1), obowi

ązuje zaleĪnoĞü rekurencyjna postaci:

1

1



˜



i

p

p

i

i

U

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

10

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

dla numerów stanów:

n

i

r

n

t

t





i

n

i

i

i

n

n

p

p

P

O

˜

˜

˜



!

0

a gdy przyjmie si

Ċ, Īe

P

O

U

, to zale

ĪnoĞü ma postaü:

n

i

i

i

n

n

p

p



˜

˜

!

0

U

(5)

W zakresie stanów systemu kiedy tworzy si

Ċ w nim kolejka zgáoszeĔ (tzw. "stany z kolejką” –

rys. 1), obowi

ązuje wiĊc zaleĪnoĞü rekurencyjna postaci:

n

p

p

i

i

U

˜

1

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

11

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

Warto

Ğü prawdopodobieĔstwa stanu S

0

wyznaczy

ü moĪna z warunku:

1

0

¦



r

n

k

k

p

Wykorzystuj

ąc równania

(4)

i

(5)

mo

Īna zapisaü, Īe:

0

!

!

!

!

2

!

1

kolejka

0

1

0

0

2

0

0

0

˜

˜





˜

˜



˜





˜



˜





























r

r

n

n

n

n

n

p

n

n

p

n

p

p

p

p

U

U

U

U

U

a st

ąd

1

!

!

!

2

!

1

1

0

0

2

0

0

0

¦

˜

˜



˜





˜



˜









r

n

n

j

n

j

j

n

n

n

p

n

p

p

p

p

U

U

U

U



i ostatecznie:

1

0

1

0

!

!









»

¼

º

«

¬

ª

¦

¦

˜



n

i

r

n

n

j

n

j

j

i

n

n

i

p

U

U

(6)

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

12

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

o

Prawdopodobie

Ĕstwo odmowy przyjĊcia zgáoszenia do obsáugi w systemie

Zdarzenie odmowy przyj

Ċcia zgáoszenia do obsáugi w systemie M/M/n/r wystĊpuje tylko wtedy

gdy w systemie znajduje si

Ċ juĪ (n+r) zgáoszeĔ, stąd:

r

r

n

r

n

strat

n

!

n

p

p

p

˜

˜





U

0

(7)

o

ĝrednia dáugoĞü kolejki

Korzystaj

ąc z zasad wyznaczania wartoĞci oczekiwanej zmiennej losowej typu dyskretnego,

Ğrednią liczbĊ zgáoszeĔ oczekujących w systemie na rozpoczĊcie obsáugi moĪna obliczyü wg formuáy:

¦ ˜



r

s

s

n

oczek

p

s

L

1

.

(8)

o

ĝrednia liczba wolnych kanaáów obsáugi

Korzystaj

ąc z zasad wyznaczania wartoĞci oczekiwanej zmiennej losowej typu dyskretnego,

Ğrednią liczbĊ wolnych kanaáów obsáugi w systemie moĪna obliczyü wg formuáy:

¦ ˜



n

k

k

n

wol

p

k

L

1

(9)

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

13

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

o

Wspó

áczynnik przestoju kanaáów obsáugi

Jest to stosunek

Ğredniej liczby wolnych kanaáów obsáugi i liczby kanaáów obsáugi stanowiska, co

wyra

Īa zaleĪnoĞü:

n

L

W

wol

przest

a po wykorzystaniu zale

ĪnoĞci (6) mamy:

n

p

k

W

n

k

k

n

¦ ˜



1

przest

(10)

o

Prawdopodobie

Ĕstwo zdarzenia, Īe wszystkie kanaáy obsáugi są zajĊte

¦



r

n

n

k

k

p

p

zaj

¦

˜

˜





r

n

n

j

n

j

j

n

n

p

p

!

0

zaj

U

(11)

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

14

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

o

ĝredni czas oczekiwania obiektów na rozpoczĊcie obsáugi

T

oczek

(na podstawie 2-giej formu

áy Little’a)

oczek

oczek

L

T

˜

O

1

(12)

o

ĝredni czas pobytu obiektów w systemie

T

sys

(na podstawie 1-szej formu

áy Little’a)

sys

sys

L

T

˜

O

1

(13)

gdzie:

zaj

oczek

sys

L

L

L



(14)

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

15

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r

PODSUMOWANIE MODELOWANIA ANALITYCZNEGO SYSTEMU

M/M/n/

r

i

Elementarny system obs

áugi z ograniczoną moĪliwoĞcią oczekiwania obiektów (zgáoszeĔ) na

obs

áugĊ:

x rozk

áad liczby (L

ob

) obiektów znajduj

ących siĊ w systemie – p(i)=P{L

ob

= i},

x prawdopodobie

Ĕstwo, Īe system jest pusty – p

0

,

x prawdopodobie

Ĕstwo, Īe wszystkie kanaáy stanowiska są zajĊte – p

zaj

,

x prawdopodobie

Ĕstwo, Īe wszystkie miejsca w kolejce są zajĊte – p

strat

,

x

Ğrednia liczba obiektów oczekujących na obsáugĊ – L

oczek

,

x

Ğrednia liczba wolnych kanaáów obsáugi – L

wol

,

x wspó

áczynnik przestoju kanaáów obsáugowych – W

przes

,

x

Ğredni czas przebywania obiektów w systemie (wg I-szej formuáy Little’a) – T

sys

,

x

Ğredni czas oczekiwania obiektów na rozpoczĊcie obsáugi (wg II-giej formuáy Little’a) –
T

oczek

.

Plik:

BO_PP_M_M_n_r_Analityczne_p_s_[v2].doc

16

/

16

A. KADZI

ēSKI,

ANALITYCZNE MODELE ELEMENTARNEGO SYSTEMU OBS

àUGI M/M/n/r