Modele kolejkowe – modele masowej obsługi

A.K. Erlang – inżynier telekomunikacyjny, początek XX w.

D.G. Kendall 1951

Dyscypliny kolejek:

• FIFO – First In First Out , PAPS (fr.)

• LIFO – Last In First Out, DAPS (fr.)

• SIRO – Select In Random Order, RSS – Random Selection for Service

Zmienne losowe w modelu masowej obsługi:

τ₁ - odstępy czasu między zgłoszeniami

τ₂ – czas obsługi jednego zgłoszenia

Parametry:

S - liczba aparatów obsługi

R - liczebność obsługiwanej populacji

p - liczba miejsc w kolejce

Określenie modelu (wg Kendalla):

typ rozkładu τ₁/ typ rozkładu τ₂/S: (R, p)

D – rozkład deterministyczny (degenerate) – stały czas obsługi

M – rozkład wykładniczy

G – dowolny rozkład o znanej wartości oczekiwanej i wariancji

Modele typu M/M są procesami Markowa.

Wskaźniki jakości działania systemu masowej obsługi (w okresie stacjonarnym)

• Oczekiwana liczba klientów w systemie

$L = \sum_{k = 0}^{S + p}{k{\bullet e}_{k}}$

• Oczekiwana długość kolejki

$L_{q} = \sum_{k = 1}^{p}{k \bullet e_{S + k}}$

• Oczekiwana liczba wolnych aparatów obsługi

$L_{f} = \sum_{k = 1}^{S}{k \bullet e_{S - k}}$

• Oczekiwana liczba zajętych aparatów obsługi

L_u = S − L_f

• Wskaźnik wykorzystania systemu

$\frac{L_{u}}{S}$

• Prawdopodobieństwo, że system jest pusty

e₀

• Prawdopodobieństwo, że klient musi czekać (pod warunkiem, że w kolejce jest miejsce)

$P_{w} = \sum_{k = S}^{S + p - 1}e_{k}$

• Prawdopodobieństwo odrzucenia zgłoszenia (odmowy obsługi)

P_d = e_S + p

Dla systemów M/M/S

• Oczekiwany czas w kolejce (wzór Little’a)

$W_{q} = \frac{1}{\lambda}L_{q}$

• Oczekiwany czas pobytu zgłoszenia w systemie

$W = W_{q} + \frac{1}{\mu}$

Najprostszy wariant modelu masowej obsługi M/M/1:(∞, p)

λ λ

…..

μ μ

Model tej kolejki - proces urodzin i śmierci o p+2 stanach

Rozkład graniczny: $e_{n} = \frac{\rho^{n}}{1 + \rho + \rho^{2} + \ldots\rho^{p + 1}}$ dla n=0,1,…,p+1,

gdzie $\rho = \frac{\lambda}{\mu}$ - wskaźnik obciążenia systemu, intensywności ruchu (utilization factor).

Przykład 1: Myjnia ma jedno stanowisko obsługi i dwa dla samochodów oczekujących. Samochody przyjeżdżają do myjni zgodnie z procesem Poissona o intensywności λ = 15 na godzinę.

Czas potrzebny na umycie samochodu ma rozkład wykładniczy z wartością oczekiwaną równą 3 minuty.

Czas do pojawienia się następnego auta ma rozkład wykładniczy z parametrem 15, czyli wartością oczekiwaną równą 4 minuty. Czas obsługi ma rozkład wykładniczy z wartością oczekiwaną równą 3 min.=1/20 godz., czyli z parametrem μ = 20.

Jeżeli proces jest w stanie i (czyli w myjni znajduje się i samochodów), to możliwe jest przejście do stanu i+1 (nowy samochód nadjedzie, zanim zostanie obsłużony pierwszy w kolejce), do stanu i-1 (pierwszy w kolejce zostanie obsłużony, zanim nadjedzie następny) lub pozostanie w stanie i. Jest to 4-stanowy (stany 0, 1, 2, 3) proces urodzin i śmierci z macierzą intensywności przejść

$\mathbf{A} = \begin{bmatrix} - 15 & 15 & \begin{matrix} 0 & \ \ \ \ \ \ \ 0 \\ \end{matrix} \\ 20 & - 35 & \begin{matrix} 15 & \ \ \ \ \ 0 \\ \end{matrix} \\ \begin{matrix} 0 \\ 0 \\ \end{matrix} & \begin{matrix} 20 \\ 0 \\ \end{matrix} & \begin{matrix} \begin{matrix} - 35 \\ 20 \\ \end{matrix} & \begin{matrix} 15 \\ - 20 \\ \end{matrix} \\ \end{matrix} \\ \end{bmatrix}$.

Rozkład graniczny e wyznaczamy rozwiązując układ równań

eA = 0,  e1 = 1, czyli

λe₀ = μe₁ λe₁ = μe₂ λe₂ = μe₃ e₀ + e₁ + e₂ + e₃ = 1

skąd otrzymujemy (dla $\rho = \frac{3}{4}$):

$e_{0} = \frac{1}{1 + \rho + \rho^{2} + \rho^{3}} = 0,366$ $e_{1} = \frac{\rho}{1 + \rho + \rho^{2} + \rho^{3}} = 0,274$ $e_{2} = \frac{\rho^{2}}{1 + \rho + \rho^{2} + \rho^{3}} = 0,206$

$e_{3} = \frac{\rho^{3}}{1 + \rho + \rho^{2} + \rho^{3}} = 0,154$.

Wskaźniki jakości działania myjni

• Oczekiwana liczba samochodów w myjni $L = \sum_{k = 0}^{3}{k{\bullet e}_{k}} = 1,149$

• Oczekiwana długość kolejki $L_{q} = \sum_{k = 1}^{2}{k \bullet e_{S + k}} = 0,51$

• Oczekiwana liczba wolnych aparatów obsługi $L_{f} = \sum_{k = 1}^{1}{k \bullet e_{S - k}} = 0,366$

• Oczekiwana liczba zajętych aparatów obsługi L_u = 1 − L_f = 0, 634

• Wskaźnik wykorzystania systemu $\frac{L_{u}}{S} = 0,634$

• Prawdopodobieństwo, że myjnia jest pusta e₀ = 0, 366

• Prawdopodobieństwo, że samochód musi czekać w kolejce do mycia $P_{w} = \sum_{k = 1}^{2}e_{k} = 0,480$

• Prawdopodobieństwo, że samochód odjedzie brudny P_d = e₃ = 0, 154

• Oczekiwany czas w kolejce $W_{q} = \frac{1}{15}L_{q} = 0,034\ godz. = 2,04\ min.$

• Oczekiwany czas w myjni $W = W_{q} + \frac{1}{20} = 0,084\ godz. = 5,04\ min.$

Przykład 2 M/M/1:(∞,∞)

Jesteś właścicielem stoiska z czekoladkami w centrum handlowym. Jako sprzedawcę zatrudniłeś swoją narzeczoną, która przyjmuje zamówienia, pakuje czekoladki i inkasuje należność. Sklepik działa od niedawna, więc zależy ci, aby klienci byli zadowoleni nie tylko z jakości czekoladek, ale również jakości obsługi. Zastanawiasz się zatem, czy narzeczona poradzi sobie sama ze sprzedażą, czy może trzeba będzie poprosić o pomoc młodszego brata.

Tym razem przyjmujemy, że pojemność kolejki jest nieskończona (w centrum handlowym jest dużo miejsca), klienci napływają zgodnie z procesem Poissona z parametrem λ = 0, 75, czas obsługi ma rozkład wykładniczy z parametrem μ = 1, czas mierzymy w minutach.

Modelem tego systemu jest nieskończony proces urodzin i śmierci z macierzą intensywności

$$\mathbf{A} = \begin{bmatrix} - \lambda & \lambda & \begin{matrix} 0 & & \\ \end{matrix} \\ \mu & - \left( \lambda + \mu \right) & \begin{matrix} \lambda & 0 & \\ \end{matrix} \\ \begin{matrix} 0 \\ \\ \\ \end{matrix} & \begin{matrix} \mu \\ \\ \\ \end{matrix} & \begin{matrix} \begin{matrix} - \left( \lambda + \mu \right) \\ \ddots \\ \\ \end{matrix} & \begin{matrix} \lambda \\ \ddots \\ \\ \end{matrix} & \begin{matrix} \\ \ddots \\ \\ \end{matrix} \\ \end{matrix} \\ \end{bmatrix}$$

λ λ

…..

μ μ

Dla nieskończonego procesu urodzin i śmierci rozkład graniczny otrzymamy rozwiązując układ równań

λe₀ = μe₁ λe₁ = μe₂ λe₂ = μe₃ … e₀ + e₁ + e₂ + e₃ + … = 1

Jeżeli tylko ρ < 1, to ${1 + \rho + \rho^{2} + \rho^{3} + \ldots}_{} = \frac{1}{1 - \rho}$

e₀ = 1 − ρ e₁ = ρ(1−ρ) e₂ = ρ²(1−ρ) …

1) zatrudnienie do pomocy młodszego brata – młodszy brat pakuje czekoladki, co skraca średni czas obsługi klienta do 45 sekund. Czas obsługi ma zatem rozkład wykładniczy z parametrem μ = 1, 25/minutę

2) przyjęcie do pracy koleżankę narzeczonej - drugiej sprzedawczyni z osobnym stanowiskiem i kasą – dodanie nowego aparatu obsługi.

Model M/M/2:(∞,∞), λ = 0, 75,  μ = 1 jest procesem urodzin i śmierci z macierzą intensywności

$$\mathbf{A} = \begin{bmatrix} - \lambda & \lambda & \begin{matrix} 0 & & \\ \end{matrix} \\ \mu & - \left( \lambda + \mu \right) & \begin{matrix} \lambda & 0 & \\ \end{matrix} \\ \begin{matrix} 0 \\ \\ \\ \end{matrix} & \begin{matrix} 2\mu \\ \\ \\ \end{matrix} & \begin{matrix} \begin{matrix} - \left( \lambda + 2\mu \right) \\ \ddots \\ \\ \end{matrix} & \begin{matrix} \lambda \\ \ddots \\ \\ \end{matrix} & \begin{matrix} \\ \ddots \\ \\ \end{matrix} \\ \end{matrix} \\ \end{bmatrix}$$

λ λ λ

….

μ 2μ 2μ

Macierz intensywności dla dowolnego S ma postać

$$\mathbf{A} = \begin{bmatrix} {- \lambda}_{0} & \lambda_{0} & \begin{matrix} 0 & & \\ \end{matrix} \\ \mu_{1} & - \left( \lambda_{1} + \mu_{1} \right) & \begin{matrix} \lambda_{1} & & 0 \\ \end{matrix} \\ \begin{matrix} 0 \\ \\ \\ \end{matrix} & \begin{matrix} \mu_{2} \\ \\ \\ \end{matrix} & \begin{matrix} \begin{matrix} - \left( \lambda_{2} + \mu_{2} \right) \\ \ddots \\ \\ \end{matrix} & \begin{matrix} \lambda_{2} \\ \ddots \\ \\ \end{matrix} & \begin{matrix} \\ \ddots \\ \\ \end{matrix} \\ \end{matrix} \\ \end{bmatrix}$$

λ_n = λ

$$\mu_{n} = \left\{ \begin{matrix} n\mu\ dla\ n \leq S \\ S\mu\ dla\ n > S \\ \end{matrix} \right.\ $$

Optymalizacja działania systemu kolejkowego – analiza kosztów

Na koszt pracy systemu składają się:

- koszt obsługi SC (service cost)

- koszt czekania WC (waiting cost)

Znając rozkład prawdopodobieństwa stanu systemu w okresie stacjonarnym, rozpatrujemy wartość oczekiwaną łącznego kosztu (TC, total cost)

E(TC) = E(SC) + E(WC)

Najprostsze podejście do analizy kosztów

TC = c_wL + c_sS

Koszt całkowity= koszt oczekiwania (jednostki czasu spędzonej w kolejce) * oczekiwana długość kolejki + koszt obsługi na jednostkę czasu * liczba serwerów

Przykład 2, cd.

Przypuśćmy, że oszacowałeś koszt oczekiwania na poziomie 10 zł/ godz., a koszt obsługi to 7 zł/godz. Który wariant – młodszy brat czy koleżanka narzeczonej jest lepszy?

	Sama	Z bratem	Z koleżanką
Stopa przybyć λ	0.75	0.75	0.75
Stopa obsługi μ	1	1.25	1
Liczba aparatów	1	1	2
Obciążenie systemu	75%	56%	37,5%
Długość kolejki	2,25	0,72	0,12
Liczba klientów w systemie	3	1,28	0,87
Prawd. że klient musi czekać	0,75	0,56	0,2
Czas w kolejce	3	0,96	0,16
Czas w systemie	4	1,71	1,16
Koszt	37	19,86	22,73

Inne systemy masowej obsługi, przykłady

Rozwiązanie w STORMie

Scenariusz 1

Twoja firma naprawia i konserwuje wyspecjalizowaną aparaturę. Posiadasz 2 urządzenia diagnostyczne i odpowiednie zespoły osób do ich obsługi. Ze względu na duży popyt na usługi Twojej firmy i tworzące się kolejki rozważasz kupno nowego urządzenia diagnostycznego. Ceny za Twoje usługi są naprawdę wysokie i nie wypada zmuszać klientów do długiego czekania na naprawienie ich cennego sprzętu. Nowe urządzenie kosztuje $1.500.000, po 20 latach eksploatacji stanie się gratem o wartości ok. $200.000. Jego amortyzacja łącznie z płacami personelu kosztuje ok. $4.600 na tydzień.

Czas obsługi jednego klienta jest zmienną losową o rozkładzie wykładniczym ze średnią 2 godziny.

W ciągu tygodnia zgłasza się przeciętnie 38 klientów. Twoi ludzie pracują 8 godzin na dobę przez 5 dni w tygodniu.

Najtrudniej jest oszacować koszt czekania klientów na wykonanie zamówienia. Po długim namyśle ustaliłeś koszt oczekiwania na naprawę równy $1000 za tydzień dla jednego klienta.

Scenariusz 2

Ponownie zadajesz sobie pytanie: czy Twoje kłopoty nie biorą się przede wszystkim z bardzo dużego zróżnicowania czasu wykonania usługi. Decydujesz się sprawdzić, co będzie, jeśli uda się zmniejszyć odchylenie standardowe czasu trwania naprawy. Gdyby mniejsze odchylenie standardowe mogło znacząco poprawić efektywność systemu, warto byłoby poczynić wysiłki w tym kierunku. Spróbujesz zmniejszyć odchylenie standardowe aż o połowę.

Scenariusz 3

Aby zmniejszyć rozmiary niezadowolenia klientów czekających na wykonanie usługi spróbuj ograniczyć długość kolejki na przykład do 10 osób. Osoby nie mieszczące się w kolejce odchodzą do konkurencji – ich stratę można wycenić jako utracony zysk, który wynosi $5000 za każdą usługę.

Scenariusz 4

Zauważasz, że najwięcej korzyści przynosi Ci obsługa 200 stałych klientów. Ogranicz swą działalność tylko do tej grupy. Przeciętnie każdy klient zgłasza się co 5 tygodni, czyli składa 0.2 zamówienia na tydzień.

Który scenariusz wybierzesz?

	Scenariusz 1	Scenariusz 2	Scenariusz 3	Scenariusz 4
Liczba aparatów obsługi	2	3	2	3
Rozkład czasu odstępów między zgłoszeniami
Intensywność zgłoszeń
Rozkład czasu obsługi
Średni czas obsługi
Odchylenie standardowe czasu obsługi
Populacja zgłoszeń
Liczba miejsc w kolejce
Tygodniowy koszt czekania klienta
Tygodniowy koszt pracy urządzenia
Koszt straty klienta
Współczynnik wykorzystania systemu
Średnia długość kolejki
P-stwo, że klient musi czekać
P-stwo odmowy obsługi
Średni czas czekania klienta w kolejce
Tygodniowy koszt ogółem działania systemu

Praca domowa (dla chętnych)

Kioskarz przeprowadził obserwacje dotyczące napływu klientów i czasu obsługi:

klient	Czas od przybycia poprzedniego klienta (w sekundach)	Czas obsługi (w sekundach)	klient	Czas od przybycia poprzedniego klienta (w sekundach)	Czas obsługi (w sekundach)
1	19	65	26	78	4
2	85	3	27	14	10
3	46	43	28	52	121
4	13	45	29	130	21
5	52	9	30	28	37
6	49	18	31	7	84
7	34	41	32	134	21
8	18	1	33	13	34
9	25	34	34	82	41
10	81	55	35	58	19
11	74	70	36	21	46
12	60	12	37	54	70
13	19	15	38	66	21
14	14	36	39	4	35
15	34	122	40	5	44
16	41	19	41	5	83
17	14	23	42	4	19
18	5	73	43	5	116
19	56	52	44	1	81
20	9	30	45	2	0
21	15	5	46	1	42
22	4	29	47	5	35
23	12	54	48	1	82
24	27	19	49	3	40
25	9	4	50	5	170

Przyjmując, że klient rezygnuje, jeśli w kolejce stoi więcej niż 5 osób, wyznacz wskaźniki jakości działania tego kiosku.