Teoria kolejek – systemy
masowej obsługi
Janusz Papliński
Teoria kolejek – systemy
masowej obsługi
Janusz Papliński
Prosty system obsługi:
Dążymy do takiej organizacji obsługi, która pozwoli na minimalizację
czasu trwania obsługi, a więc czasu straconego, przy jednoczesnej
minimalizacji kosztów funkcjonowania systemu.
Czas oczekiwania jest czasem straconym
Źródło
zadań
kolejka
Stanowisko
obsługi
Strumień
zadań
z
i
Pojęcia podstawowe:
obsługa – czynność pozwalająca zaspokoić określone potrzeby
Zgłoszenie (zadanie) – obiekt/klient/ oczekujący na obsługę,
kolejka – zbiór zgłoszeń oczekujących wg. ustalonych reguł na
obsługę,
regulamin/kolejki lub obsługi/ - zbiór reguł, wg. których zgłoszenia
tworzą kolejkę i są obsługiwane,
aparat obsługi
układ obsługi – zbiór aparatów obsługi łącznie z czynnościami przez
nie wykonywanymi,
System – model obsługi – zbiór, którego elementami są: układ
obsługi, zgłoszenia obsługiwane, oczekujący na obsługę, zgłoszenia do
systemu.
Analiza strumienia zgłoszeń
Zgłoszenia napływają w sposób przypadkowy, nieregularny
Taki proces nazywamy procesem losowym lub stochastycznym. Tu proces
ten określa prawdopodobieństwo tego, że w określonym przedziale czasu
pojawia się w układzie określona liczba zgłoszeń.
Strumień zgłoszeń opisuje funkcja losowa X(t), (t≥0),
czyli dla każdego t≥0 wartość funkcji przedstawia liczbę
zarejestrowanych zgłoszeń, które przybyły do układu w przedziale
czasu[0,t].
Stąd X(t) przyjmuje wartości 0,1,2,…,n.
),
(
}
)
(
{
t
p
n
t
X
P
n
.
0
,...,
2
,
1
,
0
t
n
gdzie
W
dowolnym
momencie
czasu
t
strumień
charakteryzuje
prawdopodobieństwo tego, że układzie znajduje się n zgłoszeń:
- prawdopodobieństwo tego, że w czasie t nadejdzie do
układu obsługi zero zgłoszeń,
Analiza strumienia zgłoszeń
Proces stochastyczny jednorodny - prawdopodobieństwo przybycia
określonej liczby zgłoszeń w przedziale czasu [t
0
, t
0
+t] nie zależy od
momentu t
0
, natomiast jedynie od długości przedziału czasu t.
Tw. 1. Każdy jednorodny proces posiada:
0
)
(
1
lim
0
0
t
t
p
t
Można to zapisać wykorzystując pojęcie nieskończenie małej wartości
wyższego rzędu
:
)
(t
),
(
)
(
1
0
t
t
t
p
gdzie: - parametr procesu zwany intensywnością zgłoszeń,
)
(
0
t
p
- nieskończenie mała wartość wyższego rzędu w porównaniu
z t, tzn. .
)
(t
0
)
(
lim
0
t
t
t
Analiza strumienia zgłoszeń
Procesem o przyrostach niezależnych nazywamy proces
stochastyczny X(t), gdzie t 0 w którym prawdopodobieństwo
wystąpienia n zgłoszeń w przedziale [t
0
, t
0
+t] nie zależy od tego ile
zgłoszeń i w jaki sposób wystąpiło do momentu t
0
.
Strumień jest strumieniem pojedynczym, jeżeli w procesie
stochastycznym X(t), gdzie t 0, brak jest możliwości pojawienia się
więcej niż jednego zgłoszenia w tym samym momencie czasu.
Strumieniem prostym nazywamy strumień spełniający warunki
strumienia jednorodnego, o przyrostach niezależnych i pojedynczy.
Analiza strumienia zgłoszeń
Tw. 2. Jeżeli strumień zgłoszeń spełnia warunki strumienia prostego, to
zmienna losowa określająca:
a/ liczbę zgłoszeń, która przybywa do układu obsługi w czasie t
jest zgodna z rozkładem Poissona o parametrze , postaci:
, n=0,1,2, ...
b/ odstępy czasu między kolejnymi zgłoszeniami są zgodne z
rozkładem wykładniczym o parametrze a funkcja gęstości jest
postaci:
.
t 0
t
n
n
e
n
t
t
p
!
)
(
)
(
t
e
t
f
)
(
Analiza strumienia zgłoszeń
Tw. 3 Intensywność zgłoszeń strumienia prostego jest równa:
wartości oczekiwanej zmiennej losowej, jaką jest liczba zgłoszeń n
w przyjętej jednostce czasu, czyli .
)
(
1
n
E
odwrotność wartości oczekiwanej zmiennej losowej, jaką jest odstęp
czasu między poszczególnymi przybyciami, czyli .
)
(
1
E
Przykład 1. Rozkład dzienny przybyć statków do portu w tabeli
poniżej. Wyznaczyć intensywność zgłoszeń statków.
i
n
L.
p
Liczba statków
przybyłych w
ciągu jednego
dnia i
Liczba
zaobserwowany
ch
zdarzeń
1
2
3
4
0
1
2
3
223
112
26
4
Liczba przybyć statków do portu w ciągu dnia jest równa:
.
Jeżeli przyjmiemy, że rozkład przybyć jest zgodny z rozkładem
Poissona, to zgodnie z Tw. 3. .
b/ prawdopodobieństwo wystąpienia i-tej ilości zgłoszeń dla t = 1
/jeden dzień/ ma postać:
dla i=1, 2, 3.
482
,
0
365
4
*
3
26
*
2
112
*
1
223
*
0
)
(
1
n
E
482
,
0
482
,
0
!
482
,
0
)
1
(
e
i
p
i
i
)
(
1
n
E
1
2
3
4
5
6
7
8
9
10
10
-10
10
-8
10
-6
10
-4
10
-3
10
-2
10
-1
10
0
c/ oczekiwana liczba dni z i-tą liczebnością przybyć:
dla i=1, 2, 3.
482
,
0
'
!
482
,
0
365
e
i
n
i
i
1
2
3
4
5
6
7
8
9
10
10
-8
10
-6
10
-4
10
-2
10
0
10
2
10
4
oczekiwana iloœæ statków
oc
ze
ki
w
an
a
ilo
œ
æ
d
ni
Analiza czasu trwania obsługi
Czas trwania obsługi ma rozkład wykładniczy o funkcji gęstości:
gdzie - intensywność obsługi
i dystrybuancie rozkładu równej:
t
e
T
P
F
1
)
(
)
(
Tw. 4. Intensywność obsługi jest odwrotnością wartości
oczekiwanej zmiennej losowej, jaką jest czas trwania obsługi
poszczególnych zgłoszeń.
e
f
*
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
System tworzą:
-
jeden aparat obsługi o wykładniczym czasie trwania
obsługi i intensywności ,
-
prosty strumień zgłoszeń o intensywności ,
-
regulamin obsługi: jeżeli aparat jest zajęty, to zgłoszenia
ustawiają się w kolejce i obsługiwane są w kolejności
przybyć.
Oznaczenia:
E(i) – stan systemu, w którym znajduje się „i” zgłoszeń,
p(t) – prawdopodobieństwo tego, że system w chwili „t”
znajdzie się w stanie E
i
, czyli .
)
(
)
(
i
i
E
p
t
p
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
System znajduje się w stanie równowagi statycznej wtedy i tylko wtedy
gdy .
n
n
t
p
t
p
)
(
lim
Jeżeli analizowany system masowej obsługi osiągnął stan równowagi
statycznej, to prawdopodobieństwa pojawienia się lub zniknięcia stanu
są takie same:
.
)
(
)
(
)
(
)
(
1
1
1
1
n
n
n
n
n
n
n
n
E
E
P
E
E
P
E
E
P
E
E
P
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
,
1
0
p
p
1
1
2
0
p
p
p
p
……………………………………….
n
n
n
n
p
p
p
p
1
1
1
1
n
n
p
E
i
i
p
E
0
0
p
E
t
0
+∆t
t
0
1
1
p
E
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
W wyniku redukcji otrzymujemy:
1
),
(
0
0
0
1
1
1
0
0
p
p
p
p
p
p
n
n
n
n
n
n
n
n
Z definicji
0
0
p
stąd
to oznacza, że .
0
1
1
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
Niech
. Iloraz oznacza intensywność ruchu.
Z tego, że
i definicji q wynika:
q
1
n
n
p
p
I. Prawdopodobieństwo tego, że w systemie znajduje się n zgłoszeń:
)
1
(
q
q
p
n
n
II.
Średnia liczba zgłoszeń znajdujących się w systemie
)
(n
E
n
n
q
q
q
q
q
nq
q
q
nq
n
n
n
n
n
1
1
)
1
(
)
1
(
)
1
(
2
0
0
I.
III Wariancja liczby zgłoszeń znajdujących się w systemie :
, .
2
0
2
2
0
2
1
)
1
(
)
var(
q
q
q
q
n
n
p
n
n
n
n
n
n
IV. Średnia liczba zgłoszeń oczekujących w kolejce :
gdzie 1-p
0
oznacza, że aparat obsługi jest zajęty.
q
q
q
n
p
n
v
1
)
1
(
2
0
V.
Średni czas przebywania w systemie :
)
1
(
q
q
n
t
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
VI. Średni czas oczekiwania na obsługę /przebywania w kolejce/ :
)
1
(
2
q
q
v
w
VII. Prawdopodobieństwo, że w systemie znajduje się mniej niż N
zgłoszeń:
N
N
n
n
N
n
n
q
q
q
p
N
n
P
1
1
)
(
1
0
1
0
System z jednym stanowiskiem obsługi i nieograniczoną
kolejką
)
(
)
(
t
qe
t
P
IX. Prawdopodobieństwo oczekiwania w systemie dłużej niż :
)
(
)
(
t
e
t
P
VIII. Prawdopodobieństwo oczekiwania w kolejce dłużej niż t:
System z ograniczona długością kolejki
Rozpatrzmy system:
-
jeden aparat obsługi o wykładniczym czasie trwania obsługi i
intensywności ,
-
prosty strumień zgłoszeń o intensywności ,
-
regulamin obsługi:
1. jeżeli liczba zgłoszeń osiągnie pewien stan, to następne zgłoszenie
musi zrezygnować z oczekiwania na realizację obsługi,
2. zgłoszenia obsługiwane są wg. kolejności przybyć.
Z analizy systemu wynika, że straty zgłoszeń spowodowane
dotrzymywania regulaminu są tym większe, im większa jest intensywność
ruchu
Przyjmijmy, że kolejka jest ograniczona do N-1 zgłoszeń i każde N-te
zgłoszenie zmuszone jest do opuszczenia systemu
Prawdopodobieństwo odmowy obsługi – rezygnacja oczekiwania na
obsługę:
N
N
N
q
q
q
p
1
1
1
System z ograniczona długością kolejki
System obsługi z nieograniczoną kolejką i n równoległych
kanałów obsługi
n
=
- średnia liczba zgłoszeń w danym odcinku czasu
n
=n - średnia liczba obsłużonych zadań w danym odcinku czasu