Wyk³ad - teoria masowej obs³ugi

Teoria masowej obsługi

Podstawowe definicje (1)

Proces masowej obsługi – proces składaj

cy si

strumie

wchodz

cy (strumie

wej

ciowy, strumie

zgłosze

) –

zgłoszenia nadchodz

ce do systemu;

system obsługi ( kanały obsługi, aparaty obsługi) – zbiór urz

dze

lub

stanowisk

wiadcz

cych obsług

zgłoszenia wraz z kolejk

zgłosze

oczekuj

cych na obsług

;

strumie

wychodz

cy (strumie

wyj

ciowy) – zbiór zgłosze

obsłu

eniu oraz zbiór zgłosze

, które zrezygnowały z obsługi.

…

obsługa

rezygnacja z obsługi

zgłoszenia

strumień

wchodzący

system obsługi

strumień

wychodzący

Podstawowe definicje (2)

Klasyfikacja systemów masowej obsługi ze wzgl

du na organizacj

obsługi:

szeregowe (obsługa zgłoszenia w kilku kanałach w

le okre

lonej

kolejno

ci);

równoległe (obsługa w jednym z kilku kanałów realizuj

cych tak

sam

obsług

);

mieszane (obsługa w kolejnych podsystemach szeregowych lub

równoległych).

…

zgłoszenia

strumień

wchodzący

system obsługi

strumień

wychodzący

…

strumień

wchodzący

system obsługi

strumień

wychodzący

zgłoszenia

Podstawowe definicje (3)

Klasyfikacja systemów masowej obsługi ze wzgl

du na zachowanie si

zgłoszenia:

ze stratami (zgłoszenie opuszcza po upływie pewnego czasu system

rezygnuj

c z obsługi);

bez strat (zgłoszenie w systemie przebywa do czasu obsłu

enia).

Klasyfikacja systemów masowej obsługi ze wzgl

du na rozmiary i istnienie

kolejki:

systemy z kolejk

ograniczon

lub nieograniczon

;

systemy z kolejk

zabronion

lub niezabronion

Podstawowe definicje (4)

Klasyfikacja systemów masowej obsługi ze wzgl

du na organizacj

kolejki

(regulamin kolejki):

FIFO – First In First Out (zgłoszenie stoj

ce na pierwszym miejscu w

kolejce jest obsługiwane jako pierwsze – „kolejka naturalna”);

LIFO – Last In First Out (zgłoszenie stoj

ce na ostatnim miejscu w

kolejce jest obsługiwane jako pierwsze);

SIRO – Selection In Random Order (losowy dobór zgłoszenia do

obsługi);

Obsługa z priorytetem (pierwsze

stwo dla zgłosze

„uprzywilejowanych”).

Charakterystyki liczbowe systemów masowej obsługi (1)

1. Strumie

zgłosze

stopa zgłosze

(liczba zgłosze

napływaj

cych do systemu obsługi w

ustalonej jednostce czasu (

rednio

)

intensywno

ść

zgłosze

(odst

p czasu pomi

dzy kolejnymi zgłoszeniami

(

rednio 1/

)

2. Obsługa

stopa obsługi (liczba zgłosze

obsługiwanych w ustalonej jednostce

czasu (

rednio

)

intensywno

ść

obsługi (czasu obsługi zgłoszenia przez jeden z s

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

rednio 1/

)

Charakterystyki liczbowe systemów masowej obsługi (2)

3. Proces obsługi

intensywno

ść

ruchu (stała Erlanga – iloraz

redniej liczby zgłosze

jaka

napływa do systemu w jednostce czasu do

redniej liczby zgłosze

jaka

e by

obsłu

ona w jednostce czasu

4. Pozostałe:

liczba zgłosze

w kolejce;

liczba zgłosze

w systemie (ł

cznie w kolejce i obsłudze);

czas oczekiwania w kolejce;

czas pobytu w systemie obsługi (ł

cznie w kolejce i obsłudze);

Charakterystyki liczbowe systemów masowej obsługi (3)

4. Pozostałe (c.d.):

czas przestoju kanału obsługi (w okresie [0,T]);

czas zaj

ci kanału obsługi (w okresie [0,T]);

liczba okresów kiedy stanowisko obsługi jest wolne (w przedziale [0,T]).

Modele systemów masowej obsługi (1)

Charakterystyka modeli systemów masowej obsługi:

charakter opisowy;

liwo

ść

wyliczenia podstawowych wielko

ci liczbowych dotycz

cych

procesu masowej obsługi;

modele optymalizacyjne masowej obsługi, jako najcz

ęś

ciej formułowane, w

których poszukuje si

optymalnej liczby kanałów obsługi kieruj

c si

kryterium

najni

szego kosztu całkowitego działania całego systemu (koszt przestoju

stanowiska obsługi w jednostce czasu, koszt utraty zgłoszenia, koszt obsługi
jednego zgłoszenia, itp.).

Modele systemów masowej obsługi (2)

Wielko

ci opisuj

ce modele systemów masowej obsługi:

ττττ

– czas upływaj

cy mi

dzy dwoma kolejnymi zgłoszeniami;

ττττ

– czas obsługi jednego zgłoszenia;

s – liczba równoległych kanałów obsługi;

R – liczebno

ść

obsługiwanej populacji (otoczenia, którego elementy mog

zgłasza

zapotrzebowanie na obsług

);

L – maksymalna liczba miejsc w kolejce.

Modele systemów masowej obsługi (3)

Model masowej obsługi powinien uwzgl

dnia

typ rozkładów prawdopodobie

stw zmiennych losowych

ττττ

oraz

ττττ

;

zale

ść

(niezale

ść

) zmiennych losowych

ττττ

oraz

ττττ

;

wielko

ci ograniczaj

ce s, R i L;

dyscyplin

kolejki (kolejno

ść

obsługi).

System kodowania modeli masowej obsługi:

) /

(

) / s (R,L)

Modele systemów masowej obsługi (4)

Oznaczenia rozkładów prawdopodobie

stw zmiennych losowych

ττττ

D – proces nielosowy (deterministyczny);

M – rozkład wykładniczy lub Poisson’a;

– rozkład Erlanga n-tego rz

du;

N – rozkład normalny;

GI – ogólny niezale

ny rozkład odst

pu czasu pomi

dzy kolejnymi

zgłoszeniami;

G – ogólny rozkład czasu obsługi.

Modele systemów masowej obsługi (5)

Przykład kodowania modeli systemów masowej obsługi:

M / E

/ 1 (

∞

, 100)

Model masowej obsługi, w którym czas pomi

dzy kolejnymi zgłoszeniami jest

zmienn

losow

o rozkładzie wykładniczym (b

liczba zgłosze

jednostce czasu ma rozkład Poissona), czas obsługi jest zmienn

losow

rozkładzie Erlanga 4-tego rz

du, model posiada jeden kanał obsługi,

populacja zgłosze

jest nieograniczona, a kolejka nie mo

e przekracza

100

zgłosze

Jednokanałowy model masowej obsługi (1)

M / M / 1 (

∞

)

Model masowej obsługi, w którym czas pomi

dzy kolejnymi zgłoszeniami jest

zmienn

losow

o rozkładzie wykładniczym (b

liczba zgłosze

jednostce czasu ma rozkład Poissona), czas obsługi jest zmienn

losow

rozkładzie wykładniczym, model posiada jeden kanał obsługi, populacja
zgłosze

jest nieograniczona, a długo

ść

kolejki jest tak

e nieograniczona.

zgłoszenia

strumień

wchodzący

system obsługi

strumień

wychodzący

[M]

FIFO

Jednokanałowy model masowej obsługi (2)

1. Strumie

zgłosze

odst

p czasu (t) pomi

dzy dwoma kolejnymi zgłoszeniami, który jest zmienn

losow

o tzw. ujemnym rozkładzie wykładniczym:

f(t) = λe

–λt

dla t

≥

z warto

oczekiwan

E(t) = 1/

oraz

wariancj

(t) = (1/

)

lub

Jednokanałowy model masowej obsługi (3)

1. Strumie

zgłosze

(c.d)

liczba zgłosze

(n) pojawiaj

ca si

w systemie w jednostce czasu o długo

(T) jest zmienn

losow

o rozkładzie Poissona:

P{n=k} = (λT)

–λT

/ k!

dla k = 0,1,2,…

z warto

oczekiwan

i wariancj

E(n) = D

(n) =

λT

Jednokanałowy model masowej obsługi (4)

2. Obsługa jednego zgłoszenia

czasu (t) obsługi zgłoszenia jest zmienn

losow

o ujemnym rozkładzie

wykładniczym:

g(t) = µe

–µt

dla t

≥

z warto

oczekiwan

E(t) = 1/

oraz

wariancj

(t) = (1/

)

Jednokanałowy model masowej obsługi (5)

3. Wybrane charakterystyki liczbowe modelu M / M / 1 (

∞

)

– oczekiwana liczba zg

osze

w jednostce czasu

1/µ

– oczekiwany czas obs

ugi jednego zg

oszenia

Intensywno

ść

ruchu (stała Erlanga):

ρ = λ

Oczekiwana liczba zgłosze

w systemie (N):

N = ρ / (1 – ρ)

Oczekiwana długo

ść

kolejki (Q):

Q = ρ

/ (1 – ρ)

Jednokanałowy model masowej obsługi (6)

Oczekiwany czas pobytu w systemie (R):

R = 1 / (µ – λ)

Oczekiwany czas pobytu w kolejce (W):

W = ρ / (µ – λ)

Prawdopodobie

stwo braku zgłosze

w systemie:

= (1 – ρ)

Prawdopodobie

stwo wyst

powania n zgłosze

w systemie:

= ρ

(1 – ρ)

Jednokanałowy model masowej obsługi (7)

Oczekiwany czas przestoju w przedziale czasu [0,T] (WT):

WT = T / (1 – ρ)

Oczekiwany czas zaj

ci w przedziale czasu [0,T] (BT):

BT = T

Oczekiwana liczba przestojów (przerw w pracy kanału) w przedziale
czasu [0,T] (FPT):

FPT = Tλ(1 – ρ)

Wielokanałowy model masowej obsługi (1)

M / M / s (

∞

)

dla s

≥

Model masowej obsługi, w którym czas pomi

dzy kolejnymi zgłoszeniami jest

zmienn

losow

o rozkładzie wykładniczym, czas obsługi jest zmienn

losow

o rozkładzie wykładniczym, model posiada s równoległych

jednorodnych kanałów obsługi, populacja zgłosze

jest nieograniczona, a

długo

ść

kolejki jest tak

e nieograniczona.

…

strumień

wchodzący

system obsługi

strumień

wychodzący

zgłoszenia

[M]

FIFO

Wielokanałowy model masowej obsługi (2)

1. Strumie

zgłosze

odst

p czasu (t) pomi

dzy dwoma kolejnymi zgłoszeniami, który jest zmienn

losow

o tzw. ujemnym rozkładzie wykładniczym:

f(t) = λe

–λt

dla t

≥

z warto

oczekiwan

E(t) = 1/

oraz

wariancj

(t) = (1/

)

lub

Wielokanałowy model masowej obsługi (3)

1. Strumie

zgłosze

(c.d)

liczba zgłosze

(n) pojawiaj

ca si

w systemie w jednostce czasu o długo

(T) jest zmienn

losow

o rozkładzie Poissona:

P{n=k} = (λT)

–λT

/ k!

dla k = 0,1,2,…

z warto

oczekiwan

i wariancj

E(n) = D

(n) =

λT

Wielokanałowy model masowej obsługi (4)

2. Obsługa jednego zgłoszenia

czasu (t) obsługi zgłoszenia jest zmienn

losow

o ujemnym rozkładzie

wykładniczym:

g(t) = µe

–µt

dla t

≥

z warto

oczekiwan

E(t) = 1/

oraz

wariancj

(t) = (1/

)

Wielokanałowy model masowej obsługi (5)

3. Wybrane charakterystyki liczbowe modelu M / M / s (

∞

)

– oczekiwana liczba zg

osze

w jednostce czasu

1/µ

– oczekiwany czas obs

ugi jednego zg

oszenia

Intensywno

ść

ruchu (stała Erlanga):

ρ = λ

sµ

Oczekiwana liczba zgłosze

w systemie (N):

N = ρ + P

[ρ

s+1

/ (s – ρ

)(s – 1)!]

Oczekiwana długo

ść

kolejki (Q):

Q = N – ρ

Wielokanałowy model masowej obsługi (6)

Oczekiwany czas pobytu w systemie (R):

R = N / λ

Oczekiwany czas pobytu w kolejce (W):

W = Q / λ

Prawdopodobie

stwo braku zgłosze

w systemie:

∑

−

)

(

Wielokanałowy model masowej obsługi (7)

Prawdopodobie

stwo wyst

powania n

≥

1 zgłosze

w systemie:











≤

−

dla

Jednokanałowy model masowej obsługi – przykład (1)

M / M / 1 (

∞

)

zgłoszenia

strumień

wchodzący

system obsługi

strumień

wychodzący

[M]

FIFO

Gniazdo produkcyjne składa si

z jednego agregatu obsługiwanego przez 1 lub

2 osoby. Przeprowadzono badanie statystyczne i stwierdzono,

e liczba detali

napływaj

ca do gniazda produkcyjnego w ci

gu 1 minuty ma rozkład Poissona

o warto

ci oczekiwanej równej 5 detali na minut

. Czas obsługi jest w ka

dym

przypadku zmienn

losow

o rozkładzie wykładniczym, o warto

ci oczekiwanej

zale

nej od liczby osób obsługuj

cych agregat.

I. 7,5 sek. przy obsłudze 1-osobowej
II. 6,0 sek. przy obsłudze 2-osobowej

Jednokanałowy model masowej obsługi – przykład (2)

Wyznacz podstawowe charakterystyki liczbowe tego systemu w obu
wariantach obsługi.

I. 1/µ = 7,5 sek./detal = 0,125 min./detal

µ = 8 detali/min.

II. 1/µ = 6,0 sek./detal = 0,100 min./detal

µ = 10 detali/min.

I. λ = 5 detali/min.
II. λ = 5 detali/min.

Stała Erlanga (intensywno

ść

ruchu)

→

wykorzystanie gniazda

produkcyjnego:

ρ = λ / µ

I. ρ = 5 / 8 = 0,625 = 62,5%
II. ρ = 5 / 10 = 0,500 = 50,0%

Jednokanałowy model masowej obsługi – przykład (3)

Oczekiwana liczba zgłosze

w systemie (N)

→

detali w gnie

dzie

produkcyjnym:

= ρ / (1 – ρ)

I. N = 0,625 / (1 – 0,625) = 1,67
II. N = 0,500 / (1 – 0,500) = 1,00

Oczekiwana długo

ść

kolejki (Q):

Q =

/ (1 –

)

I. Q = (0,625)

/ (1 – 0,625) = 1,04

II. Q = (0,500)

/ (1 – 0,500) = 0,50

Oczekiwany czas pobytu w systemie (R)

→

detalu w gnie

dzie

produkcyjnym [min.]:
R = 1 / (

–

)

I. R = 1 / (8 – 5) = 0,33
II. R = 1 / (10 – 5) = 0,20

Jednokanałowy model masowej obsługi – przykład (4)

Oczekiwany czas pobytu w kolejce (W) [min.]:
W =

/ (

–

)

I. W = 0,625 / (8 – 5) = 0,21
II. W = 0,500 / (10 – 5) = 0,10

Prawdopodobie

stwo braku zgłosze

w systemie

→

braku napływu detali

do gniazda produkcyjnego:
P

= (1 –

)

I. P

= 1 – 0,625 = 0,375

II. P

= 1 – 0,500 = 0,500

Jednokanałowy model masowej obsługi – przykład (5)

Prawdopodobie

stwo wyst

powania n zgłosze

w systemie:

(1 –

)

0,999

0,991

0,002

0,015

0,001

0,005

0,001

0,004

0,008

0,016

0,031

0,063

0,125

0,250

0,500

1,000

0,994

0,009

0,000

0,003

0,998

0,985

0,023

0,002

0,009

0,996

0,977

0,037

0,004

0,014

0,992

0,963

0,060

0,008

0,022

0,984

0,940

0,095

0,016

0,036

0,969

0,905

0,153

0,031

0,057

0,938

0,847

0,244

0,063

0,092

0,875

0,756

0,391

0,125

0,146

0,750

0,609

0,625

0,250

0,234

0,500

0,375

1,000

0,500

0,375

P{n≤k}

P{n≥k}

P{n=k}

Jednokanałowy model masowej obsługi – przykład (6)

Oczekiwany czas przestoju w przedziale czasu [0,T] (WT) [min.]:
WT = T / (1 –

)

dla T = 8h = 480 min.:
I. WT = 480 / (1 – 0,625) = 180
II. WT = 480 / (1 – 0,500) = 240

Oczekiwany czas zaj

ci w przedziale czasu [0,T] (BT)

→

czas pracy [min.]:

BT = T

dla T = 8h = 480 min.:
I. BT = 480

0,625 = 300

II. BT = 480

0,500 = 240

Oczekiwana liczba przestojów (przerw w pracy kanału) w przedziale czasu
[0,T] (FPT)

→

liczba detali obrobionych w gnie

dzie produkcyjnym

FPT = T

(1 –

)

dla T = 8h = 480 min.:
I. FPT = 480

(1–0,625) = 900

II. FPT = 480

(1–0,500) = 1200