7 teoria kolejek

background image

TEORIA KOLEJEK

TEORIA KOLEJEK

opracowanie na podstawie :

opracowanie na podstawie :

Jędrzejczyk Z., Skrzypek J., Kukuła K., Walkosz A. [1997]:

Jędrzejczyk Z., Skrzypek J., Kukuła K., Walkosz A. [1997]:

Badania operacyjne w przykładach i zadaniach,

Badania operacyjne w przykładach i zadaniach,

PWN,

PWN,

Warszawa.

Warszawa.

Leszek Smolarek [2005] :

Leszek Smolarek [2005] :

Modelowanie procesów

Modelowanie procesów

transportowych

transportowych

, Akademia Morska w Gdyni

, Akademia Morska w Gdyni

Piotr Gajowniczek [2008]

Piotr Gajowniczek [2008]

Teoria kolejek

Teoria kolejek

, Instytut

, Instytut

Telekomunikacji Politechniki Warszawskiej

Telekomunikacji Politechniki Warszawskiej

Jakub Wróblewski Elementy modelowania matematycznego.

Jakub Wróblewski Elementy modelowania matematycznego.

Systemy kolejek

Systemy kolejek

background image

MODELE MASOWEJ

MODELE MASOWEJ

OBSŁUGI

OBSŁUGI

Teoria masowej obsługi, zwana także teorią

Teoria masowej obsługi, zwana także teorią

kolejek, zajmuje się budową modeli

kolejek, zajmuje się budową modeli

matematycznych, które można

matematycznych, które można

wykorzystać w racjonalnym zarządzaniu

wykorzystać w racjonalnym zarządzaniu

dowolnymi systemami działania, zwanymi

dowolnymi systemami działania, zwanymi

systemami masowej obsługi.

systemami masowej obsługi.

Przykładami takich systemów są: sklepy,

Przykładami takich systemów są: sklepy,

porty lotnicze, podsystem użytkowania

porty lotnicze, podsystem użytkowania

samochodów przedsiębiorstwa

samochodów przedsiębiorstwa

transportowe, podsystem obsługiwania

transportowe, podsystem obsługiwania

obrabiarek itp

obrabiarek itp

.

.

background image
background image

Koszty

Koszty

$

Poziom obsługi

Całkowity

Obsługi

Niezadowolenia klienta

background image

Rozróżnia się systemy masowej obsługi:
-        z oczekiwaniem;
-        bez oczekiwania.

W SMO z oczekiwaniem zgłoszenie (obiekt zgłoszenia)
oczekuje w kolejce na obsługę,
zaś w systemie bez oczekiwania, wszystkie stanowiska
obsługi są zajęte i obiekt zgłoszenia wychodzi z
systemu nie obsłużony.

background image

Klient

Ładune

k

Przybyc

ie

Do

system

u

...

Kolejka

Stan.

Obsł.

Kolejka

Stan.

Obsł.

...

Kolejka

Stan.

Obsł.

Stan.

Obsł.

Stan.

Obsł.

Kolejka

Kolejka

...

...

...

Stan.

Obsł.

Stan.

Obsł.

background image

Charakterystyki

Charakterystyki

procent czasu zajętości wszystkich stanowisk obsługi

procent czasu zajętości wszystkich stanowisk obsługi

prawdopodobieństwo, że system nie jest pusty

prawdopodobieństwo, że system nie jest pusty

średnia liczba klientów oczekujących

średnia liczba klientów oczekujących

średnia liczba klientów oczekujących i obsługiwanych

średnia liczba klientów oczekujących i obsługiwanych

średni czas oczekiwania

średni czas oczekiwania

średni czas oczekiwania i obsługi

średni czas oczekiwania i obsługi

prawdopodobieństwo, że przybywający klient oczekuje

prawdopodobieństwo, że przybywający klient oczekuje

prawdopodobieństwo, że w systemie jest n klientów

prawdopodobieństwo, że w systemie jest n klientów

background image

W modelu tym występują zmienne losowe:

W modelu tym występują zmienne losowe:

czas upływający między wejściem do systemu dwóch

czas upływający między wejściem do systemu dwóch

kolejnych zgłoszeń;

kolejnych zgłoszeń;

czas obsługi jednego zgłoszenia przez stanowisko obsługi;

czas obsługi jednego zgłoszenia przez stanowisko obsługi;

liczba stanowisk;

liczba stanowisk;

liczebność miejsc w kolejce zgłoszeń oczekujących na

liczebność miejsc w kolejce zgłoszeń oczekujących na

obsługę.

obsługę.

Model matematyczny funkcjonowania SMO opiera się na

teorii procesów stochastycznych.

background image

Założenia modelu określają

Założenia modelu określają

1)      typ rozkładu prawdopodobieństwa

1)      typ rozkładu prawdopodobieństwa

zmiennych losowych (rozkład deterministyczny

zmiennych losowych (rozkład deterministyczny

– równe odstępy czasu), rozkład wykładniczy,

– równe odstępy czasu), rozkład wykładniczy,

rozkład Erlanga, dowolny rozkład;

rozkład Erlanga, dowolny rozkład;

2)      zależność lub niezależność zmiennych

2)      zależność lub niezależność zmiennych

losowych czasu czekania na zgłoszenie i czasu

losowych czasu czekania na zgłoszenie i czasu

obsługi;

obsługi;

3)      skończona lub nieskończona wartość liczby

3)      skończona lub nieskończona wartość liczby

stanowisk obsługi, długości poczekalni;

stanowisk obsługi, długości poczekalni;

4)      obowiązującą w systemie dyscyplinę

4)      obowiązującą w systemie dyscyplinę

obsługi

obsługi

.

.

background image

Proces wejściowy

Proces wejściowy

intensywność strumienia wejściowego -
intensywność przybywania;

liczba klientów-trend;

czas oczekiwania na klienta.

background image
background image
background image

Proces obsługi

Proces obsługi

Czas obsługi (bez czasu czekania w

Czas obsługi (bez czasu czekania w

kolejce)

kolejce)

Rozkład czasu obsługi np. wykładniczy:

P

for

(

)

,

t T t

e dx e

e

t t

x

t

t

ut

t

1

2

1

2

1

2

1

2

  

intensywność obsługi

średni czas obsługi 1/

background image

Notacja

Notacja

Kendall

Kendall

a

a

System kolejkowy opisany jest

System kolejkowy opisany jest

3

3

lub

lub

4

4

parametr

parametr

ami

ami

:

:

1/2/3

1/2/3

/4

/4

czas przybycia /czas obsługi /liczba stanowisk/liczba miejsc w

czas przybycia /czas obsługi /liczba stanowisk/liczba miejsc w

systemie

systemie

Parametr 1 – rozkład napływu

M = Markowski (rozkład Poissona) czas przybycia
D = Deterministyczny czas przybycia

Parametr 2 – rozkład czasu obsługi

M = Markowski (wykładniczy) czas obsługi
G = Dowolny rozkład czasu obsługi
D = Deterministyczny czas obsługi (jednopunktowy)

Parametr 3

Liczba stanowisk obsługi

Parametr 4

liczba miejsc w systemie (łącznie stanowiska obsługi+

liczba miejsc w systemie (łącznie stanowiska obsługi+

kolejka)

kolejka)

Jeśli jest nieskończona jest pomijana w zapisie

background image

System

System

M/M/s

M/M/s

s

s

stanowisk obsługi

stanowisk obsługi

.

.

Strumień wejściowy

Strumień wejściowy

Poisson

Poisson

z

z

param.

param.

.

.

Obsługa wykładnicza z param.

Obsługa wykładnicza z param.

.

.

background image

System

System

M/G/1

M/G/1

Czas obsługi nie musi mieć rozkładu

Czas obsługi nie musi mieć rozkładu

wykładniczego

wykładniczego

.

.

np.

np.

:

:

Naprawa telewizora

Naprawa telewizora

Badanie wzroku

Badanie wzroku

Fryzjer

Fryzjer

Model :

Strumień wejściowy Poisson z param. .

Czas obsługi o dowolnym rozkładzie, średniej m i
odchyleniu standardowym s.

Jedno stanowisko obsługi.

background image

System

System

M/D/1

M/D/1

Czas obsługi może być ustalony

Czas obsługi może być ustalony

.

.

np..

np..

Taśma produkcyjna

Taśma produkcyjna

.

.

Myjnia automatyczna

Myjnia automatyczna

.

.

Czas obsługi deterministyczny

Czas obsługi deterministyczny

Aby uzyskać system

Aby uzyskać system

M/D/1

M/D/1

w systemie

w systemie

M/G/1

M/G/1

trzeba przyjąć odchylenie standardowe równe

trzeba przyjąć odchylenie standardowe równe

0

0

(

(

= 0).

= 0).

background image

Schemat systemu masowej

Schemat systemu masowej

obsługi (SMO)

obsługi (SMO)

1 – zgłoszenia (obiekty zgłoszenia),

1 – zgłoszenia (obiekty zgłoszenia),

2 – kolejka obiektów,

2 – kolejka obiektów,

3 – stanowiska obsługi,

3 – stanowiska obsługi,

4 – przemieszczenia obiektów w systemie bez oczekiwania,

4 – przemieszczenia obiektów w systemie bez oczekiwania,

5 – przemieszczenia obiektów w systemie z priorytetem obsługi,

5 – przemieszczenia obiektów w systemie z priorytetem obsługi,

6 – przemieszczenia obiektu w systemie z oczekiwaniem,

6 – przemieszczenia obiektu w systemie z oczekiwaniem,

wej – strumień wejściowy zgłoszeń,

wej – strumień wejściowy zgłoszeń,

wyj – strumień wyjściowy obsłużonych obiektów.

wyj – strumień wyjściowy obsłużonych obiektów.

background image

W zależności od dyscypliny obsługi SMO

W zależności od dyscypliny obsługi SMO

można podzielić następująco:

można podzielić następująco:

FIFO (first in first out), czyli kolejność

FIFO (first in first out), czyli kolejność

obsługi według przybycia;

obsługi według przybycia;

SIRO (selection in random order) czyli

SIRO (selection in random order) czyli

kolejność obsługi losowa;

kolejność obsługi losowa;

LIFO (last in first out), czyli ostatnie

LIFO (last in first out), czyli ostatnie

zgłoszenie jest najpierw obsłużone;

zgłoszenie jest najpierw obsłużone;

priorytet dla niektórych obsług (5), np.

priorytet dla niektórych obsług (5), np.

bezwzględny priorytet obsługi oznacza,

bezwzględny priorytet obsługi oznacza,

że zostaje przerwane aktualnie

że zostaje przerwane aktualnie

wykonywana obsługa obiektu, a na jego

wykonywana obsługa obiektu, a na jego

miejsce wchodzi obiekt z priorytetem.

miejsce wchodzi obiekt z priorytetem.

background image
background image
background image

średnia liczba jednostek

średnia liczba jednostek

oczekujących w kolejce (tj.

oczekujących w kolejce (tj.

długość kolejki):

długość kolejki):

średni czas oczekiwania

średni czas oczekiwania

(przebywania w kolejce):

(przebywania w kolejce):

2

k

N

k

T

background image
background image
background image
background image

Teoria kolejek

Teoria kolejek

jednokanałowe systemy obsługi

jednokanałowe systemy obsługi

wielokanałowe systemy obsługi

wielokanałowe systemy obsługi

background image

K

K

anał obsługi:

anał obsługi:

stopa przybycia

stopa przybycia

- przeciętna liczba

- przeciętna liczba

klientów przypadająca na jednostkę

klientów przypadająca na jednostkę

czasu

czasu

, ma rozkład Poissona

, ma rozkład Poissona

;

;

stopa obsługi

stopa obsługi

- przeciętna liczba

- przeciętna liczba

klientów obsłużonych w jednostce

klientów obsłużonych w jednostce

czasu

czasu

, ma rozkład wykładniczy

, ma rozkład wykładniczy

;

;

liczba równoległych kanałów obsługi

liczba równoległych kanałów obsługi

r;

r;

parametr intensywności ruchu

parametr intensywności ruchu

-

-

stosunek liczby klientów

stosunek liczby klientów

przybywających do liczby klientów

przybywających do liczby klientów

obsłużonych w jednostce czasu.

obsłużonych w jednostce czasu.

background image

Założenia w

Założenia w

teoretycznym modelu:

teoretycznym modelu:

rozpatrywane są tylko sytuacje w

rozpatrywane są tylko sytuacje w

których klienci obsługiwani są

których klienci obsługiwani są

według kolejności przybywania do

według kolejności przybywania do

punktu świadczącego usługę,

punktu świadczącego usługę,

zatem wszyscy klienci są

zatem wszyscy klienci są

traktowani na równi.

traktowani na równi.

background image

Rozpatruje się dwa

Rozpatruje się dwa

przypadki:

przypadki:

Gdy układ zmierza do stanu równowagi

Gdy układ zmierza do stanu równowagi

(jeżeli obie wartości stałe) to

(jeżeli obie wartości stałe) to

prawdopodobieństwo tego, iż kolejka ma

prawdopodobieństwo tego, iż kolejka ma

określoną długość, jest stałe w każdej

określoną długość, jest stałe w każdej

jednostce czasu.

jednostce czasu.

gdy

gdy

układ jest niestabilny, a

układ jest niestabilny, a

prawdopodobieństwo długiej kolejki

prawdopodobieństwo długiej kolejki

rośnie (układ nie może nadrobić czasu w

rośnie (układ nie może nadrobić czasu w

którym był chwilowo niewykorzystany).

którym był chwilowo niewykorzystany).

r

r

background image

Przykład:

Przykład:

Na poczcie obok innych stanowisk jedno

Na poczcie obok innych stanowisk jedno

jest przeznaczone do obsługi wpłat i

jest przeznaczone do obsługi wpłat i

wypłat gotówkowych osób fizycznych.

wypłat gotówkowych osób fizycznych.

Ruch w godzinach 14-18 jest tak duży,

Ruch w godzinach 14-18 jest tak duży,

że rozważa się możliwość uruchomienia

że rozważa się możliwość uruchomienia

dodatkowego stanowiska obsługi.

dodatkowego stanowiska obsługi.

Sprawdzić, czy jest to słuszna decyzja.

Sprawdzić, czy jest to słuszna decyzja.

Poniżej podano obserwacje poczynione

Poniżej podano obserwacje poczynione

w czasie jednej z godzin szczytowych.

w czasie jednej z godzin szczytowych.

background image

Numer klienta

Czas przyjścia

liczony od
przybycia

poprzedni
ego

klienta (w
min)

Czas obsługi

klienta (w
min)

Numer klienta

Czas przyjścia

liczony od
przybycia

poprzedni
ego

klienta (w
min)

Czas obsługi

klienta (w
min)

1

0

1,5

11

1

5,5

2

0,5

2,5

12

1,5

4,5

3

1

1

13

2

4

4

1,5

2

14

1,5

3

5

1

3

15

1

2

6

2,5

5

16

2,5

1,5

7

0,5

0,5

17

3

3

8

6

1,5

18

3,5

4

9

2

2,5

19

4

4

10

1,5

6

20

3,5

3

Razem

40

60

background image

Rozwiązanie

Rozwiązanie

stopa przybycia

stopa przybycia

stopa obsługi

stopa obsługi

parametr intensywności ruchu

parametr intensywności ruchu

Zatem zachodzi nierówność

Zatem zachodzi nierówność

, czyli stopa

, czyli stopa

przybyć przewyższa stopę obsługi. Wartość

przybyć przewyższa stopę obsługi. Wartość

parametru

parametru

sugeruje, że mamy do

sugeruje, że mamy do

czynienia z układem niestabilnym, a

czynienia z układem niestabilnym, a

prawdopodobieństwo długiej kolejki się

prawdopodobieństwo długiej kolejki się

zwiększa.

zwiększa.

Osiągnięcie stanu równowagi jest tylko możliwe

Osiągnięcie stanu równowagi jest tylko możliwe

dzięki podjęciu radykalnych działań:

dzięki podjęciu radykalnych działań:

skróceniu czasu obsługi klienta

skróceniu czasu obsługi klienta

zainstalowaniu dodatkowego stanowiska obsługi.

zainstalowaniu dodatkowego stanowiska obsługi.

5

,

1

2

3

3

1

2

1

3

1

60

20

5

,

0

40

20

1

background image

Prawdopodobieństwo, że

Prawdopodobieństwo, że

w układzie brak klientów,

w układzie brak klientów,

czyli n=0 obliczamy ze

czyli n=0 obliczamy ze

wzoru:

wzoru:



1

0

!

1

!

1

)

0

(

r

i

r

r

r

i

i

n

P

background image

Przeciętna liczba

Przeciętna liczba

klientów oczekujących w

klientów oczekujących w

kolejce to:

kolejce to:

 

!

1

0

2

1

r

r

n

P

Q

r

background image

Prawdopodobieństwo, że

Prawdopodobieństwo, że

w kolejce oczekuje

w kolejce oczekuje

n

n

klientów określa wzór:

klientów określa wzór:

 



r

n

dla

r

n

P

r

r

n

dla

n

n

P

n

P

n

n

r

n

!

0

!

0

background image

Prawdopodobieństwo,

Prawdopodobieństwo,

że w kolejce oczekuje więcej niż

że w kolejce oczekuje więcej niż

n0

n0

klientów (pod warunkiem gdy

klientów (pod warunkiem gdy

) określa wzór

) określa wzór

1

0

r

n

1

0

r

n

!

0

1

0

0

0

r

r

n

P

r

n

n

P

n

n

r

background image

Prawdopodobieństwo,

Prawdopodobieństwo,

tego że czas oczekiwania w

tego że czas oczekiwania w

kolejce jest dłuższy niż

kolejce jest dłuższy niż

t0

t0

określa

określa

wzór:

wzór:

r

t

e

r

n

P

t

t

P

0

0

1

background image

Przykład

Przykład

W prywatnej przychodni

W prywatnej przychodni

stomatologicznej czynne są dwa

stomatologicznej czynne są dwa

gabinety lekarskie. Przecięty czas

gabinety lekarskie. Przecięty czas

przybycia pacjenta wynosi 3,8 na

przybycia pacjenta wynosi 3,8 na

godz., a stopa obsługi wynosi 2

godz., a stopa obsługi wynosi 2

pacjentów na godz.

pacjentów na godz.

background image

Czy system obsługi

Czy system obsługi

zmierza do stanu

zmierza do stanu

równowagi?

równowagi?

stan równowagi systemu jest

stan równowagi systemu jest

zachowany, bo

zachowany, bo

95

,

0

2

2

8

,

3

2

2

8

,

3

r

r

4

8

,

3 

background image

Ile wynosi

Ile wynosi

prawdopodobieństwo, że

prawdopodobieństwo, że

nie będzie kolejki?

nie będzie kolejki?

Prawdopodobieństwo, że nie

Prawdopodobieństwo, że nie

będzie kolejki

będzie kolejki

w poradni

w poradni

stomatologicznej

stomatologicznej

wynosi 36%.

wynosi 36%.

36

,

0

95

,

0

1

1

)

0

(

1

05

,

1

2

95

,

0

n

P

background image

Ile wynosi

Ile wynosi

prawdopodobieństwo, że

prawdopodobieństwo, że

pacjent będzie musiał

pacjent będzie musiał

oczekiwać?

oczekiwać?

Prawdopodobieństwo, że pacjent będzie musiał

Prawdopodobieństwo, że pacjent będzie musiał

oczekiwać na przyjęcie w poradni wynosi 64%.

oczekiwać na przyjęcie w poradni wynosi 64%.

64

,

0

!

2

95

,

0

2

36

,

0

95

,

0

2

0

1

0

0

2

n

P

background image

Ile wynosi

Ile wynosi

prawdopodobieństwo, że

prawdopodobieństwo, że

w kolejce znajdują się

w kolejce znajdują się

więcej niż dwie osoby?

więcej niż dwie osoby?

Prawdopodobieństwo, że w kolejce znajdują

Prawdopodobieństwo, że w kolejce znajdują

się więcej niż dwie osoby wynosi 15%.

się więcej niż dwie osoby wynosi 15%.

15

,

0

!

2

95

,

0

2

36

,

0

95

,

0

2

2

1

2

2

2

n

P

background image

Ile wynosi

Ile wynosi

prawdopodobieństwo, że

prawdopodobieństwo, że

pacjent będzie musiał

pacjent będzie musiał

oczekiwać w kolejce

oczekiwać w kolejce

dłużej niż 0,5 godz.?

dłużej niż 0,5 godz.?

Prawdopodobieństwo, że pacjent będzie musiał

Prawdopodobieństwo, że pacjent będzie musiał

oczekiwać w kolejce dłużej niż 0,5 godz. wynosi 11%.

oczekiwać w kolejce dłużej niż 0,5 godz. wynosi 11%.

r

t

e

r

n

P

t

t

P

0

0

1

3

,

0

!

2

95

,

0

2

36

,

0

95

,

0

2

1

1

1

1

2

n

P

11

,

0

35

,

0

3

,

0

3

,

0

5

,

0

95

,

0

2

5

,

0

2

e

t

P

background image

Ile przeciętnie pacjentów

Ile przeciętnie pacjentów

oczekuje w kolejce na

oczekuje w kolejce na

przyjęcie?

przyjęcie?

 

28

,

0

!

1

2

95

,

0

2

36

,

0

95

,

0

2

1

2

Q

Przeciętnie w kolejce na przyjęcie nie oczekują pacjenci.

background image

Jak wygląda sytuacja z

Jak wygląda sytuacja z

punktu widzenia

punktu widzenia

właściciela poradni?

właściciela poradni?

Sytuacja z punktu widzenia właściciela

Sytuacja z punktu widzenia właściciela

poradni dla pacjentów jest komfortowa.

poradni dla pacjentów jest komfortowa.

P

P

rawdopodobieństwo bezkolejkowego

rawdopodobieństwo bezkolejkowego

przyjęcia jest

przyjęcia jest

wynosi

wynosi

0,36.

0,36.

Małe jest prawdopodobieństwo oczekiwania

Małe jest prawdopodobieństwo oczekiwania

w kolejce więcej niż dwóch pacjentów, bo

w kolejce więcej niż dwóch pacjentów, bo

wynoszące 0,15.

wynoszące 0,15.

Bardzo małe jest prawdopodobieństwo, że

Bardzo małe jest prawdopodobieństwo, że

pacjent będzie czekał dłużej niż pół godziny,

pacjent będzie czekał dłużej niż pół godziny,

bo wynosi 0,11.

bo wynosi 0,11.

Z analizy wynika, że przeciętnie w kolejce

Z analizy wynika, że przeciętnie w kolejce

nie

nie

oczekuj

oczekuj

ą

ą

pacjen

pacjen

ci

ci


Document Outline


Wyszukiwarka

Podobne podstrony:
TEORIA KOLEJEK1
Klasyczny model Wilsona i teoria kolejek, Klasyczny model Wilsona: zamówienia są składane cyklicznie
Klasyczny model Wilsona i teoria kolejek długopis
Prezentacja Teoria kolejek
Ćwiczenie 4 Teoria kolejek MMc z ograniczoną kolejką, Dydaktyka, MPD, Tematy ćwiczeń
Teoria kolejek systemy masowej obsługi ppt
TEORIA KOLEJEK
Ćwiczenie 3 Teoria kolejek MMc ze stratami, Dydaktyka, MPD, Tematy ćwiczeń
TEORIA KOLEJEK1
TEORIA KOLEJEK1
Teoria kolejek i analiza potoków ruchu Miskiewicz Januszewski
Arkusz Teoria kolejek
teoria bledow 2
sroda teoria organizacji i zarzadzania
W10b Teoria Ja tozsamosc
Teoria organizacji i kierowania w adm publ prezentacja czesc o konflikcie i zespolach dw1
srodki transportu koleje wyklad 1

więcej podobnych podstron