Kolejkowanie na niższym poziomie

Omawiając temat kolejkowania warto wspomnieć o twórcy teorii kolejkowania (ang. Queueing theory). Agner Krarup Erlang, bo o nim mowa, opracował model oraz opisał teorię kolejkowania. Wskazał różne sposoby obsługi kolejki oraz konsekwencje zastosowania określonych rozwiązań. Jest także inicjatorem języka Erlang, za pomocą, którego można w prosty sposób zobrazować dodawanie i pobieranie spraw z kolejki.

Wrócmy do przykładu z poprzedniego wpisu i skupmy się na elemencie przejścia od zgłoszenia (niezależnie od kanału) do określonej pozycji na liście spraw. Na poniższym diagramie został zaprezentowany fragment takiego procesu. Zgłoszenie jest zapisywane jako całość a na kolejce umieszczone są wybrane dane niezbędne do zarządzania nią.

Czynność Do sprawę do kolejki, przy wykorzystaniu języka Erlang, opiera się na logice (na podstawie strony http://erlang.org/doc/man/queue.html):

in(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item),

gdy chcemy dodać sprawę na końcu listy. Natomiast:

in_r(Item, Q1 :: queue(Item)) -> Q2 :: queue(Item),

gdy dodajemy sprawę na początku listy. Potem obsługując kolejkę pobieramy zadania z początku lub końca – odpowiednio:

out(Q1 :: queue(Item)) -> {{value, Item}, Q2 :: queue(Item)} | {empty, Q1 :: queue(Item)} 
lub
out_r(Q1 :: queue(Item)) ->{{value, Item}, Q2 :: queue(Item)} | {empty, Q1 :: queue(Item)}

Obsługując kolejkę metodą FIFO lub LIFO musimy wykorzystać pary metod:
dla FIFO – funkcja in do umieszczania oraz funkcja out do pobierania,
dla LIFO – funkcja in oraz funkcja out_r,

Metody LIFO i FIFO opisywałem w poprzednim wpisie.

Reklama

Kolejkowanie po raz drugi

Opisując proces oparty o kolejkowanie spraw pominąłem kilka istotnych kwestii. Po pierwsze, nie wskazałem, czy dany serwisant obsługuje jeden punkt sprzedaży czy więcej punktów. Po drugie, nie wyjaśniłem w jaki sposób sprawy mogą być pobierane z listy do wykonania.

Załóżmy, że na listę spraw trafiają sprawy od różnych salonów i różnymi kanałami. Wpadają na listę i są układane np. po dacie wpłynięcia. Taka lista została zasygnalizowana na diagramie. Serwisant pobierając zadania z listy ma dwie możliwości:

• pobieranie pierwszej (najstarszej) sprawy z listy – jest to obsługa oparta o zasadę FIFO, czyli z ang. First in, first out – pierwsze wchodzi, pierwsze wychodzi. Lista spraw/obiektów obsługiwana zgodnie z tą zasadą jest nazywana kolejką (ang. queue).
• pobieranie ostatniej (najnowszej) sprawy z listy – jest to obsługa oparta o zasadę LIFO, czyli z ang. Last in, First out – ostatnie wchodzi, pierwsze wychodzi. Lista spraw/obiektów obsługiwana zgodnie z tą zasadą jest nazywana stosem (ang. stack).

System może zgodnie z jedną z tych zasad, przydzielać zadanie do serwisanta.

Każda z zasad została przedstawiona na diagramie w oparciu o przykładowy proces. W sytuacji, gdy następuje szybki przyrost spraw, czas realizacji spraw z początku listy wydłuża się przy stosowaniu zasady LIFO. Z kolei stosowanie zasady FIFO w takiej sytuacji, nie wydłuża czasu realizacji zadań z listy, ponieważ dla każdej kolejnej sprawy całkowity czas realizacji z punktu widzenia Klienta obejmuje czas rzeczywistej realizacji sprawy powiększony o czas potrzebny na realizację wcześniejszych spraw z kolejki. Przy zasadzie LIFO czas oczekiwania może rosnąć, jeżeli między podjęciem sprawy X, ostatniej w danym momencie, a zakończeniem obecnie realizowanej, trafi kolejna sprawa na kolejkę. Taka sytuacja może się powtarzać kilkakrotnie. Powyższy przykład obrazuje różnicę oraz konsekwencje kolejności obsługi spraw obiektów umieszczonych odpowiednio na kolejce lub stosie.