Efektywność systemów

informatycznych

Wykład 8

TEMAT:Niemarkowskie sieci

kolejkowe

2

Rozkład Coxa



Zmienna losowa

Zmienna losowa

X

X

ma rozkład Coxa, jeśli można

ma rozkład Coxa, jeśli można

jej wartość interpretować, jako czas

jej wartość interpretować, jako czas

przechodzenia pojedynczego zgłoszenie przez

przechodzenia pojedynczego zgłoszenie przez

system przedstawiony na poniższym rysunku:

system przedstawiony na poniższym rysunku:



Zgłoszenie trafia do systemu k stacji

Zgłoszenie trafia do systemu k stacji

(serwerów) i porusza się w nim według

(serwerów) i porusza się w nim według

następujących zasad:

następujących zasad:



Czas pobytu w

Czas pobytu w

i-tej

i-tej

stacji jest zmienną losową o

stacji jest zmienną losową o

rozkładzie

rozkładzie

wykładniczym z parametrem

wykładniczym z parametrem





i

i

,

,



Po opuszczeniu

Po opuszczeniu

i-tej

i-tej

stacji, zgłoszenie z

stacji, zgłoszenie z

prawdopodobieństwem

prawdopodobieństwem

b

b

i

i

trafia do stacji

trafia do stacji

i+1-

i+1-

szej,

szej,

a z prawdopodobieństwem

a z prawdopodobieństwem

1-b

1-b

i

i

opuszcza system.

opuszcza system.

1

1

2

2

k

k

b

b

0

0

1-b

1-b

0

0

b

b

1

1

1-b

1-b

1

1

b

b

2

2

1-b

1-b

2

2

b

b

k

k

=0

=0

1-b

1-b

k

k

=1

=1

3

Rozkład Coxa - 2



Rozkład zmiennej losowej

Rozkład zmiennej losowej

X

X

określa dystrybuanta:

określa dystrybuanta:

gdzie:

gdzie:

(8.1)

(8.1)

Jeśli

Jeśli

to

to

Wynika stąd, że

Wynika stąd, że

A

A

i

i

oznacza prawdopodobieństwo,

oznacza prawdopodobieństwo,

tego, że zgłoszenie dojdzie do i-tej stacji. Z (8.1)

tego, że zgłoszenie dojdzie do i-tej stacji. Z (8.1)

wynika, że:

wynika, że:

(8.3)

(8.3)

)

(

...

...

....

)

(

)

1

(

)

(

)

1

(

1

}

{

)

(

2

1

1

1

0

2

1

2

1

0

1

0

1

0

x

F

F

F

b

b

b

x

F

F

b

b

b

x

F

b

b

b

x

X

P

x

F

k

k















































0

,

,..

1

,

1

)

(











k

x

i

b

k

i

e

x

F

i



))

(

(

)

(

*

x

F

L

s

f

s



)

2

.

8

(

:

)

1

(

1

)

(

1

0

1

1

0

*































i

r

r

i

k

i

i

j

j

j

i

i

b

A

gdzie

s

b

A

b

s

f











k

j

j

j

A

X

E

1

}

{



4

Rozkład Coxa - 3



Rozkład zmiennej Coxa jest jest uogólnieniem

Rozkład zmiennej Coxa jest jest uogólnieniem

rozkładu wykładniczego:

rozkładu wykładniczego:

- rozkład wykładniczy

- rozkład wykładniczy



Za pomocą dystrybuanty rozkładu Coxa można

Za pomocą dystrybuanty rozkładu Coxa można

przybliżyć z dowolna dokładnością dystrybuantę

przybliżyć z dowolna dokładnością dystrybuantę

dowolnego rozkładu ciągłego.

dowolnego rozkładu ciągłego.



Rozkład Coxa o k fazach oznacza się jako

Rozkład Coxa o k fazach oznacza się jako

C

C

k

k

.

.

x

e

x

F

x

F

b

b

1

1

)

(

)

(

1

,

1

1

1

0















5

Sieci niemarkowskie



W dalszym ciągu, będą rozpatrywane sieci

W dalszym ciągu, będą rozpatrywane sieci

spełniające następujące założenia:

spełniające następujące założenia:



występuje wiele typów węzłów:

występuje wiele typów węzłów:



M|M|n (typ 1),

M|M|n (typ 1),



*|C

*|C

k

k

|PS (typ 2),

|PS (typ 2),



*|C

*|C

k

k

|IS = *|C

|IS = *|C

k

k

|

|





(typ 3), (IS – infinite server)

(typ 3), (IS – infinite server)



*|C

*|C

k

k

|LIFO-PR (typ 4).

|LIFO-PR (typ 4).



występuje

występuje

R

R

klas (typów) zgłoszeń,

klas (typów) zgłoszeń,

R

R

={1,...,R}

={1,...,R}

– zbiór numerów typów zgłoszeń,

– zbiór numerów typów zgłoszeń,



Przed rozpoczęciem analizy sieci niemarkowskich

Przed rozpoczęciem analizy sieci niemarkowskich

omówione zostanie analiza pojedynczych

omówione zostanie analiza pojedynczych

systemów kolejkowych wymienionych wyżej typów.

systemów kolejkowych wymienionych wyżej typów.



Analizując pojedyncze systemy, zakładamy, że

Analizując pojedyncze systemy, zakładamy, że

zgłoszenia

zgłoszenia

r-tego

r-tego

typu

typu

przybywają do nich zgodnie ze

przybywają do nich zgodnie ze

strumieniem Poissona o intensywności

strumieniem Poissona o intensywności

.

.

r



6

Sieci niemarkowskie - 2



Przyjmujemy do dalszej analizy następujące oznaczenia:

Przyjmujemy do dalszej analizy następujące oznaczenia:

- rozkład Coxa o

- rozkład Coxa o

J

J

r

r

fazach obsługi dla zgłoszenia

fazach obsługi dla zgłoszenia

r-tego

r-tego

typu,

typu,

- parametr rozkładu czasu trwania

- parametr rozkładu czasu trwania

s-tej

s-tej

fazy czasu

fazy czasu

obsługi

obsługi

zgłoszenia

zgłoszenia

r-tego

r-tego

typu,

typu,

- prawdopodobieństwo przejścia do fazy

- prawdopodobieństwo przejścia do fazy

(s+1)-szej

(s+1)-szej

po

po

zakończeniu fazy

zakończeniu fazy

s-tej

s-tej

,

,

- prawdopodobieństwo osiągnięcia fazy

- prawdopodobieństwo osiągnięcia fazy

s

s

, przy

, przy

czym

czym

dla

dla

s=J

s=J

r

r

mamy

mamy

b

b

rs

rs

=0

=0

,

,

Średni czas obsługi zgłoszenia

Średni czas obsługi zgłoszenia

r-tego

r-tego

typu:

typu:

Przez

Przez

oznaczymy współczynnik obciążenia systemu przez

oznaczymy współczynnik obciążenia systemu przez

zgłoszenia

zgłoszenia

r-tego

r-tego

typu, a współczynnik obciążenia

typu, a współczynnik obciążenia

systemu wszystkimi typami zgłoszeń wyniesie:

systemu wszystkimi typami zgłoszeń wyniesie:

.

.

r

J

C

rs











1

0

s

i

ri

rs

b

A

rs

b







r

J

s

rs

rs

r

A

1

1





r

r

r















R

r

r

1





7

Węzeł typu 1 (M|M|n||FIFO)



Przyjmuje się założenie, że w węźle tego typu

Przyjmuje się założenie, że w węźle tego typu

wszystkie zgłoszenia mają jednakowy

wszystkie zgłoszenia mają jednakowy

wykładniczy rozkład czasu obsługi z

wykładniczy rozkład czasu obsługi z

parametrem

parametrem





. Charakterystyki graniczne dla

. Charakterystyki graniczne dla

systemów tej klasy zostały omówione w

systemów tej klasy zostały omówione w

wykładach wcześniejszych.

wykładach wcześniejszych.

8

Węzeł typu 2 (*|C|n|PS)



Jako model funkcjonowania węzła rozpatrzmy

Jako model funkcjonowania węzła rozpatrzmy

proces:

proces:

- liczba zgłoszeń typu

- liczba zgłoszeń typu

r

r

, które w chwili

, które w chwili

t

t

znajdują się w

znajdują się w

s-tej

s-tej

fazie obsługi.

fazie obsługi.

Zbiór stanów procesu można zdefiniować

Zbiór stanów procesu można zdefiniować

następująco:

następująco:

Przyjmijmy dodatkowe oznaczenia:

Przyjmijmy dodatkowe oznaczenia:

- liczba zgłoszeń r-tego typu w węźle,

- liczba zgłoszeń r-tego typu w węźle,

- liczba wszystkich zgłoszeń w węźle.

- liczba wszystkich zgłoszeń w węźle.









)

(

),..,

(

)

(

gdzie

,

)

(

),..,

(

)

(

1

1

t

X

t

X

t

X

t

X

t

X

t

X

r

rJ

r

r

R





)

(t

X

rs

}

,..

1

,

,..,

1

,..},

2

,

1

,

0

{

),

,...,

(

:

)

,...,

(

{

1

1

R

r

J

s

n

n

n

n

n

n

n

r

rs

rJ

r

r

R

r













X







r

J

s

rs

r

n

n

1







R

r

r

n

n

1

9

Węzeł typu 2 (*|C|n|PS) - 2

Można wykazać, że

Można wykazać, że

X(t)

X(t)

jest jednorodnym procesem

jest jednorodnym procesem

Markowa klasy DC. Jeśli

Markowa klasy DC. Jeśli

, to jego rozkład

, to jego rozkład

graniczny określony jest zależnościami:

graniczny określony jest zależnościami:

(8.4)

(8.4)

Jeśli interesuje nas jedynie liczba zgłoszeń

Jeśli interesuje nas jedynie liczba zgłoszeń

określonych typów, to rozpatrujemy następujący

określonych typów, to rozpatrujemy następujący

proces:

proces:

, gdzie:

, gdzie:

- liczba zgłoszeń r-tego typu w węźle.

- liczba zgłoszeń r-tego typu w węźle.

Zbiór stanów procesu

Zbiór stanów procesu

Y(t)

Y(t)

:

:

1





X

















































n

A

n

n

n

n

R

r

J

s

n

rs

rs

r

rs

R

n

r

rs

,

!

1

!

)

1

(

)

,..,

(

1

1

1















)

(

),...,

(

)

(

1

t

Y

t

Y

t

Y

R



)

(t

Y

r

}

,..},

2

,

1

,

0

{

:

)

,...,

(

{

1

R

Y











r

y

R

y

y

y

r

R

R

10

Węzeł typu 2 (*|C|n|PS) - 3



Można wykazać, że jeśli

Można wykazać, że jeśli

, to rozkład

, to rozkład

graniczny procesu

graniczny procesu

Y(t)

Y(t)

, określają zależności:

, określają zależności:

(8.4.A)

(8.4.A)



Przy dalszej agregacji stanu, kiedy interesuje

Przy dalszej agregacji stanu, kiedy interesuje

nas jedynie liczba wszystkich zgłoszeń łącznie,

nas jedynie liczba wszystkich zgłoszeń łącznie,

rozpatrujemy proces:

rozpatrujemy proces:

Jego rozkład graniczny określają zależności:

Jego rozkład graniczny określają zależności:

(8.4.B)

(8.4.B)

1

































R

r

r

R

r

r

y

r

t

y

y

y

y

y

y

y

t

Y

P

r

1

1

:

gdzie

,

!

!

)

1

(

}

)

(

{

lim

Y















R

r

r

t

Y

t

Z

1

..}

,

2

,

1

,

0

{

),

(

)

(

Z

Z

















z

z

t

Z

P

z

t

z

,

)

1

(

}

)

(

{

lim







11

Węzeł typu 3 (*|C|IS)



Proces

Proces

X(t)

X(t)

opisujący stan węzła jest identyczny

opisujący stan węzła jest identyczny

jak dla systemu typu 2. Jego rozkład graniczny

jak dla systemu typu 2. Jego rozkład graniczny

jest określony, w tym przypadku, zależnościami:

jest określony, w tym przypadku, zależnościami:

(8.5)

(8.5)



Po agregacji stanów, rozpatrujemy proces

Po agregacji stanów, rozpatrujemy proces

Y(t)

Y(t)

i

i

otrzymujemy następujący rozkład graniczny:

otrzymujemy następujący rozkład graniczny:

(8.5.A)

(8.5.A)



Dla procesu

Dla procesu

Z(t)

Z(t)

, postać rozkładu granicznego

, postać rozkładu granicznego

jest następująca:

jest następująca:

(8.5.B)

(8.5.B)

X













































n

A

n

e

R

r

J

s

n

rs

rs

r

rs

n

r

rs

,

!

1

1

1









Y













y

y

e

R

r

r

y

r

y

r

1

!







..}

,

2

,

1

,

0

{

,

!









z

z

e

z

z







12

Węzeł typu 4 (*|C

k

|LIFO-PR )



Węzeł typu 4 pracuje w ten sposób, że zgłoszenie

Węzeł typu 4 pracuje w ten sposób, że zgłoszenie

przybywając do systemu, przerywa obsługę

przybywając do systemu, przerywa obsługę

aktualnie obsługiwanego zgłoszenia (jeśli system

aktualnie obsługiwanego zgłoszenia (jeśli system

przed jego przybyciem nie był pusty) i trafia do

przed jego przybyciem nie był pusty) i trafia do

kanału obsługi. Zgłoszenie, którego obsługę

kanału obsługi. Zgłoszenie, którego obsługę

przerwano, trafia na pierwsze miejsce w kolejce.

przerwano, trafia na pierwsze miejsce w kolejce.

W momencie zwolnienia się kanału obsługi,

W momencie zwolnienia się kanału obsługi,

obsługa tego zgłoszenia jest kontynuowana od

obsługa tego zgłoszenia jest kontynuowana od

miejsca, w którym ja przerwano.

miejsca, w którym ja przerwano.



Jako model funkcjonowania węzła przyjmuje się

Jako model funkcjonowania węzła przyjmuje się

proce

proce

X(t)

X(t)

o następującej przestrzeni stanów:

o następującej przestrzeni stanów:



Przyjmuje się, że zgłoszeniem obsługiwanym jest

Przyjmuje się, że zgłoszeniem obsługiwanym jest

zgłoszenie

zgłoszenie

, pozostałe zaś oczekują w kolejce.

, pozostałe zaś oczekują w kolejce.

}

..,

,

1

},

..,

,

2

,

1

{

,

:

))

,

(

...,

),

,

((

{

1

1

n

i

J

s

r

s

r

s

r

n

i

r

i

i

n

n











R

X

)

,

(

n

n

s

r

13

Węzeł typu 4 (*|C

k

|LIFO-PR ) - 2



Rozkład graniczny procesu

Rozkład graniczny procesu

X(t)

X(t)

określają zależności:

określają zależności:

Warunkiem istnienia rozkładu granicznego jest

Warunkiem istnienia rozkładu granicznego jest

spełnienie warunku

spełnienie warunku

.

.



Rozkład graniczny procesu

Rozkład graniczny procesu

określają

określają

zależności:

zależności:

(8.6.A)

(8.6.A)



Rozkład graniczny procesu

Rozkład graniczny procesu

Z(t)

Z(t)

, określony jest

, określony jest

następująco:

następująco:

(8.6.B)

(8.6.B)

)

.

(

n

A

s

r

s

r

n

j

s

r

s

r

r

n

n

n

j

j

j

j

j

6

8

,

)

1

(

))

,

(

...,

),

,

((

1

,

)

,

(

1

1

X









































1









R





r

r

t

Y

t

Y

)

(

)

(

























R

r

r

R

R

r

r

y

r

y

y

y

y

y

y

y

y

r

1

1

1

..,

,

,

!

!

)

1

(







...}

,

2

,

0

{

,

)

1

(









z

z

z







14

Model ruchu zgłoszeń w sieci



Przyjmujemy, że zgłoszenia poruszają się w sieci

Przyjmujemy, że zgłoszenia poruszają się w sieci

zgodnie z poniższymi założeniami:

zgodnie z poniższymi założeniami:



każde zgłoszenie porusza się w sieci niezależnie od

każde zgłoszenie porusza się w sieci niezależnie od

innych zgłoszeń,

innych zgłoszeń,



jeśli zgłoszenie znajdzie się w konkretnym węźle to

jeśli zgłoszenie znajdzie się w konkretnym węźle to

jego dalsza droga zależy jedynie od numeru tego

jego dalsza droga zależy jedynie od numeru tego

węzła, a nie zależy od dotychczasowej jego drogi,

węzła, a nie zależy od dotychczasowej jego drogi,

przejście zgłoszenia między węzłami wewnętrznymi

przejście zgłoszenia między węzłami wewnętrznymi

sieci opisuje macierz.

sieci opisuje macierz.



Ruch zgłoszeń w sieci opisuje macierz

Ruch zgłoszeń w sieci opisuje macierz

Q

Q

0

0

:

:

gdzie:

gdzie:

oznacza prawdopodobieństwo tego, że

oznacza prawdopodobieństwo tego, że

zgłoszenie

zgłoszenie

r-tego

r-tego

typu opuszczając

typu opuszczając

i-ty

i-ty

węzeł trafi

węzeł trafi

do węzła

do węzła

j-tego

j-tego

stając się zgłoszeniem

stając się zgłoszeniem

s-tego

s-tego

typu.

typu.

 

R

W







s

r

j

i

js

ir

q

Q

,

,

,

0

0

js

ir

q

,

15

Model ruchu zgłoszeń w sieci - 2



Jeśli przez

Jeśli przez

X

X

k

k

oznaczymy proces, którego

oznaczymy proces, którego

(i,r)

(i,r)

oznacza, że zgłoszenie w

oznacza, że zgłoszenie w

k-tym

k-tym

kroku znajduje

kroku znajduje

się węźle

się węźle

i-tym

i-tym

i jest

i jest

r-tego

r-tego

typu, to zbiór stanów

typu, to zbiór stanów

tego procesu jest następujący:

tego procesu jest następujący:



Z definicji wynika, ze proces

Z definicji wynika, ze proces

X

X

k

k

jest procesem

jest procesem

Markowa klasy DD o macierzy

Markowa klasy DD o macierzy

prawdopodobieństw przejść w jednym kroku

prawdopodobieństw przejść w jednym kroku

określonej zależnością:

określonej zależnością:



Dwa typy zgłoszeń nazwiemy wymienialnymi,

Dwa typy zgłoszeń nazwiemy wymienialnymi,

jeśli

jeśli

 

R

W











s

r

j

i

js

ir

q

Q

,

,

,

0

0

}

0

{

}

,

:

)

,

{(

0

0









R

W

X

r

i

r

i





0

)

(

0

)

(

,

,

,

0

,

0

,

0

,















t

p

p

k

l

j

i

t

kr

ls

js

ir





W

16

Model ruchu zgłoszeń w sieci - 3

gdzie

gdzie

prawdopodobieństwo przejścia ze stanu

prawdopodobieństwo przejścia ze stanu

(i,r)

(i,r)

do stanu

do stanu

(j,s)

(j,s)

po czasie

po czasie

t

t

nie przechodząc przez stan 0.

nie przechodząc przez stan 0.



Relacja wymienialności jest relacją równoważności

Relacja wymienialności jest relacją równoważności

(zwrotna, symetryczna i przechodnia). Zatem zbiór

(zwrotna, symetryczna i przechodnia). Zatem zbiór

typów zgłoszeń można podzielić na klasy

typów zgłoszeń można podzielić na klasy

równoważności:

równoważności:

a,

a,

K

K

jest zbiorem numerów klas równoważności.

jest zbiorem numerów klas równoważności.



Jeśli

Jeśli

R

R

k

k

jest klasą równoważności typów

jest klasą równoważności typów

(wymienialnych) to w zbiorze stanów

(wymienialnych) to w zbiorze stanów

X

X

0

0

łańcucha

łańcucha

X

X

k

k

można wyróżnić następujący podzbiór:

można wyróżnić następujący podzbiór:

Zbiór powyższy nazywa się łańcuchem stanów

Zbiór powyższy nazywa się łańcuchem stanów

osiągalnych przez zgłoszenia typów należących do

osiągalnych przez zgłoszenia typów należących do

zbioru

zbioru

R

R

k

k

.

.

)

(

0

,

t

p

js

ir

)

(

,

oraz















l

k

k

k

l

k

R

R

K

R

R

K



l

k

r

r

i

l

k

k

k













,

}

:

)

,

{(

R

R

R

X

X

R

X

17

Model ruchu zgłoszeń w sieci - 4



Uwzględniając rozłączność łańcuchów stanów

Uwzględniając rozłączność łańcuchów stanów

osiągalnych dla różnych klas równoważności

osiągalnych dla różnych klas równoważności

typów zgłoszeń, można rozpatrywać sieć

typów zgłoszeń, można rozpatrywać sieć

kolejkową rozbitą na podsieci, w których ruch

kolejkową rozbitą na podsieci, w których ruch

zgłoszeń opisany będzie procesami

zgłoszeń opisany będzie procesami

X

X

k

k

o

o

zbiorach stanów

zbiorach stanów

.

.



Zgłoszenia z tych podsieci poruszają się

Zgłoszenia z tych podsieci poruszają się

niezależnie od siebie, ale wspólnie obciążają

niezależnie od siebie, ale wspólnie obciążają

niektóre węzły sieci kolejkowej.

niektóre węzły sieci kolejkowej.



Jeśli

Jeśli

, to łańcuch jest

, to łańcuch jest

zamknięty. Przyjmuje się, że krąży w nim stała

zamknięty. Przyjmuje się, że krąży w nim stała

liczba zgłoszeń.

liczba zgłoszeń.



Jeśli

Jeśli

, to

, to

łańcuch jest otwarty.

łańcuch jest otwarty.

k

R

X

k

ir

ir

q

q

R

X









r)

(i,

dla

0

0

0

,

,

0

)

0

0

(

)

,

(

),

,

(

0

,

,

0











js

ir

q

q

r

i

s

j

k

R

X

18

Model ruchu zgłoszeń sieci - 5



Zgłoszenia do sieci napływają zgodnie ze

Zgłoszenia do sieci napływają zgodnie ze

strumieniem Poissona, którego intensywność

strumieniem Poissona, którego intensywność

może być zależna od stanu sieci:

może być zależna od stanu sieci:



Intensywność

Intensywność

, gdzie liczba zgłoszeń w

, gdzie liczba zgłoszeń w

całej sieci,

całej sieci,



Intensywność

Intensywność

, gdzie

, gdzie

jest liczbą zgłoszeń w

jest liczbą zgłoszeń w

k-tym łańcuchu

k-tym łańcuchu

.

.



Jeśli strumień wejściowy jest niezależny od stanu

Jeśli strumień wejściowy jest niezależny od stanu

systemu to

systemu to

jeśli jest jeden sumaryczny strumień wejściowy,

jeśli jest jeden sumaryczny strumień wejściowy,

jeśli zgłoszenia napływają osobno do

jeśli zgłoszenia napływają osobno do

każdego łańcucha.

każdego łańcucha.

k

R

X

)

(n



n

)

(

k

n



k

n







)

(n

K





k

n

k

k

,

)

(





19

Model ruchu zgłoszeń w sieci - 6



Układ równań równowagi (równania ruchu)

Układ równań równowagi (równania ruchu)

(8.7)

(8.7)



Układy dla poszczególnych łańcuchów stanów

Układy dla poszczególnych łańcuchów stanów

osiągalnych można rozwiązać niezależnie.

osiągalnych można rozwiązać niezależnie.



Interpretacje wielkości występujących w układzie

Interpretacje wielkości występujących w układzie

(8.7)

(8.7)



- względna częstość wizyt zgłoszenia r-tego typu w

- względna częstość wizyt zgłoszenia r-tego typu w

węźle i-tym (oczekiwana liczba wizyt w i-tym węźle

węźle i-tym (oczekiwana liczba wizyt w i-tym węźle

zgłoszenia r-tego typu miedzy dwiema kolejnymi

zgłoszenia r-tego typu miedzy dwiema kolejnymi

bytnościami w węźle 0) – dla sieci otwartych,

bytnościami w węźle 0) – dla sieci otwartych,



- intensywność strumienia zgłoszeń r-tego

- intensywność strumienia zgłoszeń r-tego

typu trafiających z otoczenia do węzła i-tego,

typu trafiających z otoczenia do węzła i-tego,



- intensywność strumienia zgłoszeń r-tego

- intensywność strumienia zgłoszeń r-tego

typu trafiających z otoczenia do węzła i-tego,

typu trafiających z otoczenia do węzła i-tego,

k

k

R

R

js

js

r

i

js

ir

ir

s

j

e

q

q

e

X

X













)

,

(

,

0

)

,

(

,

ir

e

ir

k

q

,

0





ir

k

e





20

Model ruchu zgłoszeń w sieci - 7



Układ (8.7) (URR) posiada jednoznaczne

Układ (8.7) (URR) posiada jednoznaczne

rozwiązanie jeśli

rozwiązanie jeśli

jest łańcuchem otwartym.

jest łańcuchem otwartym.



Dla łańcucha zamkniętego istnieje rozwiązanie

Dla łańcucha zamkniętego istnieje rozwiązanie

jednoznaczne z dokładnością do mnożenia przez

jednoznaczne z dokładnością do mnożenia przez

stałą.

stałą.



URR dla łańcucha zamkniętego

URR dla łańcucha zamkniętego

ma

ma

następująca postać:

następująca postać:



Rozpatrzmy dowolne rozwiązanie

Rozpatrzmy dowolne rozwiązanie

i

i

dokonajmy przekształcenia:

dokonajmy przekształcenia:

dla ustalonego

dla ustalonego

k

R

X

l

R

X

l

l

R

R

js

r

i

js

ir

ir

s

j

e

q

e

X

X











)

,

(

)

,

(

,

 

 

l

s

j

js

ir

js

e

e

e

e

R

X









)

,

(

*

*

1

 

l

s

j

js

e

e

R

X





)

,

(

l

r

i

R

X



)

,

(

21

Model ruchu zgłoszeń w sieci - 8



Wektor

Wektor

e

e

*

*

posiada następujące własności:

posiada następujące własności:



e

e

*

*

jest również rozwiązaniem URR,

jest również rozwiązaniem URR,



,

,



oznacza oczekiwaną liczbę wizyt

oznacza oczekiwaną liczbę wizyt

zgłoszenia s-tego typu w j-tym węźle między kolejnymi

zgłoszenia s-tego typu w j-tym węźle między kolejnymi

wizytami tego zgłoszenia w i-tym węźle jako

wizytami tego zgłoszenia w i-tym węźle jako

zgłoszenia r-tego typu.

zgłoszenia r-tego typu.

1

*



ir

e

)

,

(

)

,

(

dla

r

i

s

j

e

js



22

Sieci BCMP



Biorąc pod uwagę omówione wcześniej typy

Biorąc pod uwagę omówione wcześniej typy

węzłów oraz typy zgłoszeń, sieć BCMP [Baskett,

węzłów oraz typy zgłoszeń, sieć BCMP [Baskett,

Chandy, Munz, Palacios 1976] możemy określić

Chandy, Munz, Palacios 1976] możemy określić

następująco:

następująco:



Uwzględniając występowanie w sieci wielu

Uwzględniając występowanie w sieci wielu

typów zgłoszeń przyjmijmy następujące

typów zgłoszeń przyjmijmy następujące

oznaczenia dla ustalonego i-tego węzła:

oznaczenia dla ustalonego i-tego węzła:

- liczba faz w rozkładzie Coxa zgłoszeń r-tego

- liczba faz w rozkładzie Coxa zgłoszeń r-tego

typu

typu

- prawdopodobieństwo osiągnięcia s-tej fazy

- prawdopodobieństwo osiągnięcia s-tej fazy

obsługi przez zgłoszenia r-tego typu,

obsługi przez zgłoszenia r-tego typu,





}

4

,

3

,

2

,

1

{

kolejki

regulamin

:

gdzie

,

,

,

,

,

,

,

,

0

0









i

i

i

i

i

i

BCMP

typ

f

i

typ

f

n

C

M

Q

S

W

R

W



ir

J

irs

A

23

Sieci BCMP - 2

- intensywność obsługi w s-tej fazie zgłoszeń

- intensywność obsługi w s-tej fazie zgłoszeń

r-tego typu,

r-tego typu,

- oczekiwany czas obsługi zgłoszeń r-tego

- oczekiwany czas obsługi zgłoszeń r-tego

typu,

typu,

- liczba zgłoszeń r-tego typu w s-tej fazie

- liczba zgłoszeń r-tego typu w s-tej fazie

obsługi w stanie

obsługi w stanie

n

n

,

,

-

-

liczba zgłoszeń r-tego typu w stanie n,

liczba zgłoszeń r-tego typu w stanie n,

- liczba zgłoszeń w i-tym węźle w stanie n,

- liczba zgłoszeń w i-tym węźle w stanie n,

irs



ir



1

irs

n

ir

n

i

n

ir

k

ir

ir

ir

ir

e



















1

k



-

-

intensywność

intensywność

napływu zgłoszeń do k-

napływu zgłoszeń do k-

tego łańcucha

tego łańcucha







R

r

ir

i

1





- współczynnik obciążenia węzła.

- współczynnik obciążenia węzła.

24

Sieci BCMP - 3



Jako model funkcjonowania sieci BCMP

Jako model funkcjonowania sieci BCMP

przyjmujemy proces stochastyczny

przyjmujemy proces stochastyczny

X(t)

X(t)

o

o

następującej przestrzeni stanów:

następującej przestrzeni stanów:

wezle

tym

-

i

w

kolejce

w

zgloszenia

tego

-

j

typ

4

jesli

))

,

(

),..,

,

(

),..,

,

((

)

,..,

,..,

(

3

,

2

jesli

)

,..,

,..,

(

wezle

tym

-

i

w

w

zgloszenia

kolejce

w

tego

-

j

typ

1

jesli

)

,..,

,..,

(

:

)

,..,

,..,

(

{

1

1

1

1

1

1























ij

i

n

i

n

i

ij

ij

i

i

i

irJ

irs

ir

ir

i

iR

ir

i

i

ij

i

n

i

ij

i

i

W

i

r

typ

s

r

s

r

s

r

n

n

n

n

n

typ

n

n

n

n

r

typ

r

r

r

n

n

n

n

n

i

i

r

i

X

25

Sieci BCMP - 4



Twierdzenie 8.1. BCMP

Twierdzenie 8.1. BCMP

Jeśli we wszystkich węzłach sieci BCMP spełnione

Jeśli we wszystkich węzłach sieci BCMP spełnione

sa warunki ergodyczności (tzn.:

sa warunki ergodyczności (tzn.:

dla węzłów

dla węzłów

typu: 1,2,4) to rozkład graniczny procesu

typu: 1,2,4) to rozkład graniczny procesu

X(t)

X(t)

istnieje i jest określony następującymi

istnieje i jest określony następującymi

zależnościami:

zależnościami:

gdzie:

gdzie:

G

G

stała normalizacyjna,

stała normalizacyjna,

(8.8)

(8.8)

1



i



)

(

)..

(

..

)

(

)

(

}

)

(

{

lim

)

(

1

1

1

W

W

i

i

t

n

p

n

p

n

p

n

d

G

n

t

X

P

n

p





























i

ij

n

j

i

ir

i

i

e

n

p

1

)

(



dla węzłów typu 1 (FIFO)

dla węzłów typu 1 (FIFO)









































R

r

J

s

n

irs

irs

ir

irs

i

i

i

ir

irs

A

e

n

n

n

p

1

1

!

1

!

)

(



dla węzłów typu 2 (PS)

dla węzłów typu 2 (PS)

26

Sieci BCMP - 5









i

ij

ij

ij

ij

ij

n

j

s

ir

s

ir

ir

i

i

A

e

n

p

1

)

(



dla węzłów typu 4 (LIFO-PR)

dla węzłów typu 4 (LIFO-PR)







































R

r

J

s

n

irs

irs

ir

irs

i

i

ir

irs

A

e

n

n

p

1

1

!

1

)

(



dla węzłów typu 3 (IS)

dla węzłów typu 3 (IS)

Stałą normalizacyjną

Stałą normalizacyjną

G

G

wyznaczamy z warunku:

wyznaczamy z warunku:

1

)

( 



X

n

n

p

Stałą

Stałą

d(n)

d(n)

definiuje się następująco:

definiuje się następująco:

gdzie

gdzie

- liczba zgłoszeń w k-tym łańcuchu

- liczba zgłoszeń w k-tym łańcuchu

stanów osiągalnych

stanów osiągalnych

, jeśli intensywność

, jeśli intensywność

napływu zgłoszeń zależy od liczby zgłoszeń w

napływu zgłoszeń zależy od liczby zgłoszeń w

sieci,

sieci,











K

k

n

l

k

k

l

n

d

1

1

0

)

(

)

(



k

n

k

R

X

(8.9

(8.9

)

)

27

Sieci BCMP - 6

─

jeśli intensywność napływu zgłoszeń nie zależy

jeśli intensywność napływu zgłoszeń nie zależy

od stanu sieci:

od stanu sieci:

w szczególności, jeśli K=1 to

w szczególności, jeśli K=1 to







K

k

n

k

k

n

d

1

)

(



n

n

d





)

(

(8.9A)

(8.9A)

(8.9B)

(8.9B)

28

Zagregowane modele sieci BCMP



Jeśli interesuje nas jedynie liczba zgłoszeń

Jeśli interesuje nas jedynie liczba zgłoszeń

poszczególnych typów w poszczególnych

poszczególnych typów w poszczególnych

węzłach sieci, to modelem sieci BCMP będzie

węzłach sieci, to modelem sieci BCMP będzie

proces:

proces:

- liczba zgłoszeń r-tego typu w i-tym węźle

- liczba zgłoszeń r-tego typu w i-tym węźle

w chwili t,

w chwili t,

Zbiór stanów procesu

Zbiór stanów procesu

Y(t)

Y(t)

:

:

)

(

),..,

(

),..,

(

(

)

(

))

(

),..,

(

(

)

(

1

1

t

Y

t

Y

t

Y

t

Y

t

Y

t

Y

t

Y

iR

ir

i

i

W





)

(t

Y

ir

..}}

,

1

,

0

{

),

,..,

(

:

)

,..,

(

{

1

1









ir

iR

i

i

W

y

y

y

y

y

y

y

Y

29

Zagregowane modele sieci BCMP - 2



Wykorzystując rozkład graniczny procesu

Wykorzystując rozkład graniczny procesu

X(t)

X(t)

oraz definicję procesu

oraz definicję procesu

Y(t)

Y(t)

, można pokazać, że:

, można pokazać, że:

gdzie:

gdzie:

)

(

)..

(

)

(

)}

(

{

lim

)

(

1

1

1

W

W

t

y

g

y

g

y

d

G

t

Y

P

y

p

















i

ir

y

i

y

ir

R

r

ir

i

i

i

e

y

y

y

g







































1

!

1

!

)

(

1

dla węzłów typu 1

dla węzłów typu 1

ir

y

ir

ir

R

r

ir

i

i

i

e

y

y

y

g

























1

!

1

!

)

(

dla węzłów typu 2 i 4

dla węzłów typu 2 i 4

ir

y

ir

ir

R

r

ir

i

i

e

y

y

g























1

!

1

)

(

dla węzłów typu 3

dla węzłów typu 3

(8.10

(8.10

)

)

30

Zagregowane modele sieci BCMP - 3



Najbardziej zagregowany opis sieci uzyskamy

Najbardziej zagregowany opis sieci uzyskamy

rozpatrując proces:

rozpatrując proces:

gdzie:

gdzie:

liczba wszystkich zgłoszeń w i-

liczba wszystkich zgłoszeń w i-

tym wężle w chwili

tym wężle w chwili

t

t

.

.

Zbiór stanów procesu

Zbiór stanów procesu

Z(t)

Z(t)

:

:

Można wykazać, ze rozkład graniczny procesu

Można wykazać, ze rozkład graniczny procesu

Z(t)

Z(t)

ma postać:

ma postać:

dla węzłów typu 1, 2,

dla węzłów typu 1, 2,

4

4

dla węzłów typu

dla węzłów typu

3.

3.

))

(

..,

),

(

(

)

(

1

t

Z

t

Z

t

Z

W



)

(t

Z

i

,..}}

2

,

1

,

0

{

:

)

..,

,

(

{

1







i

W

z

z

z

z

Z















W

i

i

i

t

z

p

z

t

Z

P

z

p

1

)

(

}

)

(

{

lim

)

(

gdzie:

gdzie:

i

z

i

i

i

i

z

p











)

1

(

)

(

i

i

e

z

z

p

i

z

i

i

i











!

)

(

(8.11

(8.11

)

)