Wyższa Szkoła Informatyki i Zarządzania

w Bielsku-Białej

Wydział Informatyki

Kierunek: Informatyka

Specjalność: Systemy informatyczne

Specjalizacja: Informatyczne Systemy Projektowania

PRACA DYPLOMOWA INŻYNIERSKA

Temat : Komputerowy Symulator Systemu M/M/2

Dyplomant : Andrzej Kuś

Promotor : dr hab. inż. J. Kałuski, prof. ndzw.

Bielsko-Biała, 2006

Ja niżej podpisany - świadom odpowiedzialności oświadczam, że praca dyplomowa nt.: „Komputerowy Symulator Systemu M/M/2” została napisana samodzielnie.

Ponadto oświadczam, że:

1. Praca ta nie narusza praw autorskich w rozumieniu ustawy z dnia 4 lutego 1994 o prawie autorskim i prawach pokrewnych (Dz. Ustaw z 2000 roku, Nr 80, poz. 904, z późniejszymi zmianami) oraz dóbr osobistych chronionych prawem autorskim.

2. Praca ta nie zawiera danych i informacji, które uzyskałem w sposób niedozwolony.

3. Praca ta nie była wcześniej podstawą żadnej innej urzędowej procedury związanej z nadawaniem dyplomów wyższej uczelni lub tytułów zawodowych. Uczelni w rozumieniu przepisów o szkolnictwie wyższym przysługuje pierwszeństwo w opublikowaniu pracy dyplomowej studenta. Jeżeli uczelnie nie opublikowała pracy dyplomowej w ciągu 6 miesięcy od jej obrony, student, który ją przygotował, może ją opublikować, chyba, że praca dyplomowa jest częścią utworu zbiorowego (Dz. Ustaw z 2000 roku, Nr 80, poz. 904, z późniejszymi zmianami). Uczelnia może wdrożyć rezultaty pracy dyplomowej poprzez Centrum Transferu Technologii.

.............................................

Pracę tę dedykuję mojej mamie Krystynie Kuś, której zawdzięczam możliwość studiowania na tej uczelni.

Spis treści

1. WSTĘP

1. Geneza pracy

Jednym z najszybciej rozwijających się gałęzi badań operacyjnych jest teoria masowej obsługi, zwaną również teorią kolejek. Jest to dziedzina matematyczna, która zajmuje się analizowaniem systemów, w których powstają kolejki. Już przed pierwszą wojną światową A.K. Erlang (Dania) obserwował centrale telefoniczne do swoich badań stochastycznych, którego model obsługi dzwoniących w określonym czasie abonamentów jest dobrym tematem teorii kolejek[2]. Był to nie wątpliwie impuls do dalszego rozwijania tej dziedziny, której celem było konstruowanie i rozwiązywanie modeli matematyczno-statycznych, obsłużenia w jak najkrótszym czasie większej liczby klientów(zgłoszeń). Aczkolwiek pojęcie teorii masowej obsługi po raz pierwszy w roku 1955 sformułował radziecki matematyk A. J. Chinczin. W Polsce natomiast pierwotnie tematem tym zajmował się W. Sadowski[12].

Badania nad centralą telefoniczną oczywiście nie są jedynym zainteresowaniem teorii kolejkowej. Następnymi przykładami może być obsługa biurowa(np. bank, poczta, urząd itp.), duże sklepy przemysłowe(supermarkety), stacje benzynowe, komunikacja, transport a nawet kolejki w służbie zdrowia. Również teleinformatyka oraz sieci komputerowe(pierwsze badania dotyczyły sieci Ethernet) stały się dziś jedną z najważniejszych domen zastosowań kolejkowych. Wszystkie te zagadnienia można rozważać dwoma metodami: analitycznymi i symulacyjnymi[1]. Do tej pierwszej grupy metod zaliczamy stosunkowo prostsze systemy, których metoda rozwiązania sprowadza się do ułożenia równań różniczkowych. Natomiast do policzenia bardziej złożonych i dokładnych obliczeń metoda druga(symulacyjna) sprawdza się znakomicie, do czego nieodzownym i bezcennym narzędziem jest komputer.

W niniejszej pracy zaprezentowano właśnie taką metodę do symulacji dwu-kanałowego systemu M/M/2. Symulacją systemu kolejkowego rozumiemy jako proces umożliwiający analizę zachowania się systemu po przez obserwację zachowania się jego modelu. Jest to eksperyment stochastyczny polegający na losowaniu przez program komputerowy czasu pomiędzy wejściami „klientów” do systemu oraz czasu obsługi tych zgłoszeń na podstawie zadanych przez nas parametrów(intensywności). Po wykonaniu dostatecznie dużej ilości powtórzeń symulacji(iteracji) przy wprowadzonych przez nas danych dostajemy uśrednione wyniki, które są bardziej dokładne niż obliczenia analityczne[2].

2. Cel pracy

Celem niniejszej pracy jest stworzenie programu komputerowego, który umożliwi symulację systemu obsługi zgłoszeń typu M/M/2.

3. Teza pracy

Symulator Komputerowy Systemu M/M/2 umożliwi symulacje dwu-kanałowego systemu obsługi M/M/2 z dyscypliną zgłoszeń FIFO oraz nieograniczoną kolejką. Z jego pomocą można określonej ilości kanałów obsługi przy zakładanej intensywności zgłoszeń oraz obsługi przeprowadzić symulacje i pokazać średnie wyniki w zależności od liczby symulacji, co pozwoli na znalezienie jak najlepszego rozwiązania.

4. Zakres pracy

W odniesieniu do tak uściślonego celu i tezy pracy, w rozdziale drugim omówione zostały wybrane zagadnienia z systemów obsługi masowej, definiując podstawowe pojęcia i terminologie, typy i klasyfikacje systemów oraz analityczne metody analizy systemów kolejkowych (rozdz. 2.1). Dodatkowo w rozdziale tym, przedstawione są konkretne typy systemów kolejkowych wraz z przykładowymi zadaniami, zaczynając od systemu z ograniczoną liczbą zgłoszeń w kolejce M/M/m/FIFO/m+N, przez system jedno-kanałowy M/M/1 i ostatecznie kończąc na dwu-kanałowym systemie obsługi M/M/2 (rozdz. 2.2). W rozdziale trzecim ukazany jest zastosowany w programie komputerowym algorytm. W czwarty rozdziale zademonstrowana została realizacja tego algorytmu w programie przy różnych danych. Wnioski końcowe i spostrzeżenia omawianego tematu wypisano w piątym rozdziale. W rozdziale szóstym podano spis literatury cytowanej w książce oraz praktyczniej przy projekcie symulatora. Ostatni siódmy rozdział zawiera streszczenie pracy w języku angielskim.

2. WYBRANE ZAGADNIENIA Z SYSTEMÓW OBSŁUGI MASOWEJ (SOM)
   

1. Podstawowe pojęcia związanie z SOM

W teorii kolejek jednym z najważniejszych pojęć jest zgłoszenie, rozumiane jako żądanie wykonania przez system jakieś określonej czynności, obsłużenia(np. samochód na stacji paliw chce zatankować). Natomiast obsługą nazywamy spełnienie tego żądania(np. zatankowania pojazdu).

Procesem przybywania do systemu zgłoszeń oraz czasem obsługi w systemie rządzi ciąg zdarzeń losowych, inaczej mówiąc strumieniem zdarzeń.

Rys.2.1 Ogólny schemat systemu kolejkowego[1]

Na przedstawionym wyżej rysunku(Rys.2.1) widzimy(od lewej) strumień wejściowy czyli ciąg zgłoszeń udających się do systemu. Następnym krokiem jest udanie się bezpośrednio do kanału obsługi w przypadku wolnego kanału. Natomiast gdy kanał bądź kanały(w zależności od systemu) są zajęte wtedy zgłoszenie zatrzymuje się w poczekalni i dopiero po zwolnieniu miejsca w kanale podąża dalej(do kanału obsługi). Gdy zgłoszenie znajduję się na wyjściu systemu wtedy nosi miano strumienia wyjściowego, przy czym wcale nie musi zostać obsłużone. Wobec tego strumień ten może zawierać zgłoszenia obsłużone jak i nie obsłużone.

1. Zadania i środki formalne systemów kolejkowych

Najważniejszym zadaniem teorii kolejek jest minimalizacja czasu oczekiwania zgłoszenia na obsługę i kosztów obsługi klienta. Oczekiwanie klienta w kolejce jest również stratą pieniężną dla przedsiębiorców gdyż przez ten czas można było by obsłużyć większą liczbę zgłoszeń po przez zwiększenie kanałów obsługi. Z drugiej zaś strony otwarcie(dodanie) większej liczby obsługi zgłoszeń może również doprowadzić „przedsiębiorcę” na straty finansowe, ze względu na możliwość niedociążenia systemu obsługi(puste, nieobsługiwane punkty obsługi). W teorii kolejek szuka się zatem optymalizacji(równowagi) , między długością kolejki a systemem obsługi, aby straty poniesione przez odbierającego zgłoszenia były jak najmniejsze(zminimalizowane).

Długość kolejki zależy głownie od trzech rzeczy: strumienia zgłoszeń(statyczny opis przybywania do systemu zgłoszeń), procesu obsługi(realizacja obsługi zgłoszeń) oraz regulaminu(dyscypliny) kolejki czyli kodeksu kiedy i na jakich zasadach następne zgłoszenie wejdzie do systemu obsługi(np. w opracowywanym systemie M/M/2 gdy się zwolni miejsce).

Obsługa natomiast jest czasem wymaganym do obsługi jednego zgłoszenia i krotności systemu obsługi(ilość zgłoszeń które mogą być w tym samym czasie obsługiwane).

Załóżmy, że zgłoszenia są losowe, a odstęp czasu między kolejnymi zgłoszeniami(interwał) jest zmienną losową to średnie natężenie strumienia zgłoszeń wynosi:

gdzie: λ - średnie natężenie strumienia zgłoszeń,

- średnia długość interwału pomiędzy dwoma sąsiadującymi zgłoszeniami.

Jeżeli czas obsługi zgłoszenia w systemie nie jest stały wtedy opisany jest przy pomocy odpowiedniej funkcji rozkładu:

gdzie:
- parametr rozkładu,

- średni czas obsługi zgłoszenia.

Ostatnim elementem wpływającym na nasycenie(długość) kolejki jest jej regulamin czyli kolejność wybierania zgłoszeń będących w poczekalni. Poniżej przedstawiam różne sposoby(dyscypliny)[3]:

• FIFO (z ang. First-In, First-Out) - pierwsze do obsługi kieruje się zgłoszenie najdłużej oczekujące w poczekalni(kolejce).

• LIFO (z ang. Last-In, First-Out) - pierwsze do obsługi kieruje się zgłoszenie, które przybyło jakie ostatnie(np. wysiadanie pasażerów z windy).

• RSS (z ang. Random Selection for Service) - następne zgłoszenie które wejdzie do systemu jest losowane.

• RR (z ang. Round-Robin) - zgłoszenia są obsługiwane według regulaminu FIFO, z tym że mają ograniczony czas obsługi. Obsługa jest przerywana na końcu przedziału Q(quantum). Jeśli obsługa przed upływem czasu się nie zakończyła, to zgłoszenie natychmiast wraca do kolejki z prawdopodobieństwem σ, lub opuszcza system gdy udało się zakończyć obsługę.

• PS (z ang. Proccesor-Sharing) - dyscyplina ta reprezentuje graniczny przypadek obsługi RR:
  , gdzie S jest zmienną losową opisującą czas trwania obsługi w systemie.

Wyżej wymienione przypadki dotyczą oczywiście systemów, w których zgłoszenia stoją w kolejce oczekując na obsługę. Może się również tak zdarzyć, że klient opuści kolejkę, np. przez zbyt długi czas oczekiwania lub wielkość kolejki, wtedy mamy dodatkowe ograniczenia, które należy wziąć pod uwagę(niecierpliwego klienta).

1. 
   Typy systemów obsługi masowej

Przez pojęcie typ systemu obsługi masowej rozumiemy tu, jaki los spotka te zgłoszenia, które w chwili pojawienia się zastają wszystkie urządzenia obsługi(kanały obsługi) zajęte. Poniżej przedstawiam następujące typy systemów[10]:

• Systemy ze stratami - zgłoszenia w chwili pojawienia się nie zastają wolnego kanału obsługi. Te zgłoszenia zostają stracone.

• Systemy z oczekiwaniem - istnieje możliwość czekania na obsługę przez dowolnie wiele zgłoszeń. Zgłoszenia te tworzą kolejkę, a regulamin kolejki ustala w jakiej kolejności wybierane są do obsługi czekające w kolejce zgłoszenia(sposoby obsługi kolejek - rozdz. 2.1.1.)

• Systemy kombinowane (z oczekiwaniem i ze stratami) - oczekiwać może tylko określona liczba zgłoszeń, reszta jest tracona. Tracone mogą być również zgłoszenia, których czas przebywania lub oczekiwania przekroczy pewien ustalony limit czasowy.

• Systemy z priorytetami - pojawiające się zgłoszenia posiadają różne pierwszeństwa.

1. Klasyfikacja systemów obsługi masowej

Do skróconego oznaczenia systemów obsługi masowej, ciągów zgłoszeń oraz ciągów obsługi używa się symboliki wprowadzonej przez D. Kendalla. Podane w [1] oraz w [3] oznaczenia są opisane w następujący sposób:

X/Y/m/r,

gdzie:

X - symbol rozkładu wejściowego strumienia zgłoszeń,

Y - symbol rozkładu czasów obsługi zgłoszeń,

m - ilość kanałów obsługi,

r - dopuszczalna długość kolejki.

Symbol X oraz Y przyjmujemy jako postać następujących rozkładów:

D - rozkład deterministyczny lub regularny,

M - rozkład wykładniczy czasu obsługi lub odstępów czasu między sąsiednimi klientami(zgłoszeniami),

- rozkład Erlanga k-tego rzędu, występujące jako zgłoszenie jak i urządzenie obsługujące,

- rozkład hiperwykładniczy rzędu r,

- rozkład Coxa rzędu k,

GI - strumień ogólnego typu, dowolny oraz niezależny,

G - strumień o dowolnym rozkładzie czasów obsługi.

Dla przykładu przedstawię trzy rodzaje systemów. GI/M/1 oznacza system, którego strumień zgłoszeń jest nie poisson'owski (rekurencyjny), posiada on ciąg niezależnych czasów obsługi o rozkładzie wykładniczym oraz jeden kanał obsługi zgłoszeń. System o poisson'owskim strumieniu zgłoszeń, posiadający ciąg niezależnych czasów obsługi o dowolnym rozkładzie i jeden kanał obsługi oznaczymy M/G/1. Natomiast system M/M/1 posiada poisson'owski strumień zgłoszeń, a ciąg czasów obsługi jest rozkładem wykładniczym z jednym kanałem obsługi.

Rozwinięciem symboliki Kendalla (w którym nie ma mowy o ilości zgłoszeń przebywających w systemie oraz dyscypliny kolejki czy też czy jest to system otwarty bądź zamknięty) jest kod A.M Lee. Symbol ten jeszcze w ostatnich latach został rozwinięty o dodatkowy element(ostatni) i ma postać:

X/Y/m/d/l/r,

gdzie:

X - symbol rozkładu wejściowego strumienia zgłoszeń,

Y - symbol rozkładu czasów obsługi zgłoszeń,

d - dyscyplina kolejki (Rozdz. 2.1.1.),

l - maksymalna liczba zgłoszeń mogących pomieścić się w systemie,

r - rodzaj systemu(czy jest otwarty - O, bądź zamknięty - F).

W takim razie kod M/
/4/FIFO/∞/O będzie oznaczał system, którego system zgłoszeń jest poisson'owski, rozkład czasu obsługi Coxa rzędu drugiego, posiadający cztery kanały obsługi. Zgłoszeniem które najpierw wchodzi do obsługi jest te, które oczekuje najdłużej w kolejce(poczekalni) posiadającej nieskończoną ilość miejsca, z kolei system obsługi jest systemem otwartym.

2. Analityczne metody analizy systemów kolejkowych
   

Jak już wspomniałem analityczna metoda analizy systemów kolejkowych sprowadza się do ułożenia i rozwiązania układów równań różniczkowych, które wiążą za sobą prawdopodobieństwa zdarzeń występujących w procesie obsługi zgłoszeń. Metody te można stosować do rozwiązania stosunkowo prostych systemów(problemów) obsługi masowej przy założeniach dotyczących strumieni zgłoszeń i czasów obsługi zgłoszeń.

Powracając do ogólnego opisu systemu kolejkowego, posiadamy trzy zasadnicze elementu: proces wejścia, poczekalnie(kolejkę) oraz obsługę. Każdy z tych trzech elementów ma wielkie znaczenie dla obsługi. Pierwszą i podstawową rzeczą w systemach kolejkowych jest to z jaką intensywnością czasu przychodzą następne po sobie zgłoszenia. Wyznacza to strumień zgłoszeń gdzie kolejne elementy zgłaszające się do systemu obsługi przyjmowane się w pewnych losowych odstępach czasu. Najczęściej przyjmuje się, że odstępy te są zmiennymi losowymi niezależnymi, o jednakowym rozkładzie prawdopodobieństwa. Szczególną rolę ma tu tzw. proces Poissona, w którym prawdopodobieństwo pojawienia się k zgłoszenia w t przedziale czasu określa się:

gdzie:

k = 0,1,2, ...

λ - intensywność strumienia wejściowego,

Strumień poisson'owski to strumień, gdzie liczba klientów nadchodzących w jednostce czasu jest zmienną losową, która podlega rozkładowi Poisson'a o parametrze λ, a odstęp czasowy między zgłaszającymi się klientami jest zmienną losową o rozkładzie wykładniczym o parametrze λ. Poniżej przedstawiam rozkład dystrybuanty Poisson'a.

Rys. 2.2 Rozkład Poisson'a dla różnych
(obwiednia rozkładu dyskretnego)

Mówimy, że zmienna losowa X ma rozkład wykładniczy, jeżeli jej gęstość prawdopodobieństwa ma postać:

, dla

Rys. 2.3 Rozkład wykładniczy

Dystrybuanta tego rozkładu jest następująca:

, dla

Natomiast przyjmując y = F(x), zapiszemy:

, dla

Następnie po przekształceniu powyższego równania względem t, otrzymujemy:

.

Przekształcenie takie pozwala na generowaniu liczb losowych metodą odwróconej dystrybuanty. Funkcja ta, służy do generowania ciągu liczb pseudolosowych o rozkładzie prawdopodobieństwa, będącym jednoznacznym funkcją zmiennej niezależnej.

Niech R będzie zmienną losową o rozkładzie równomiernym na przedziale
, czyli o rozkładzie, która dostarcza nam funkcja random( )[7]. Natomiast za F przyjmijmy pewną ciągłą i ściśle rosnącą funkcją taką, iż F(-∞)=O, F( +∞ )=1 (czyli dystrybuantą pewnej zmiennej losowej). Zdefiniujemy nową zmienną losową

Ponieważ

P{X ≤ x} =P{F^-1(R) ≤ x} = P{R ≤ F(x)} = F(x),

to zmienna losowa X ma rozkład o dystrybuancie F . Wynika stąd, że jeśli (r_n ), n=1,2,..., jest ciągiem liczb losowych o rozkładzie równomiernym na przedziale (0,1), to ciąg (x_n ), n = l,2..., dla x_n = F^-1 (r_n ), jest ciągiem liczb losowych o rozkładzie z dystrybuantą F.

Dla ogólnego przypadku metoda ta jest bardzo uciążliwa, wymaga bowiem wyznaczania skomplikowanych całek. Wobec tego stosuje się różne metody przybliżone, korzystając ze znanych aproksymacji.

1. Omówienie markowskich systemów kolejkowych wraz z przykładami

Definicja: Proces scholastyczny X(t) jest nieskończoną rodziną zmiennych losowych, określonych na tej samej przestrzeni probabilistycznej i uporządkowanych według parametru t (w naszym przypadku czasu), tzn. dla każdej dopuszczalnej wartości t = t_i określona jest dystrybuanta

Fx(x, t_i) = P[X(t_i)
].

Wartości przyjmowane przez proces tworzą jego przestrzeń stanu, która może być ciągła lub dyskretna; w tym ostatnim przypadku proces nazywamy łańcuchem. Również parametr indeksujący t przybiera wartości ciągłe lub dyskretne - mówimy odpowiednio o procesach z ciągłym lub dyskretnym czasem. Procesy z dyskretnym czasem nazywane są łańcuchami.

Zależności statystyczne pomiędzy X(t) dla różnych wartości t należy opisać za pomocą n-wymiarowej dystrybuanty

określonej dla wszystkich wartości n i wszystkich dopuszczalnych

.

W ogólnym przypadku jest to zadanie niewykonalne; trzeba przyjąć dodatkowe założenia o procesie, np. ograniczyć się do procesów stacjonarnych, dla których

gdzie

Poniżej będzie nas interesowała szczególna klasa procesów : procesy Markowa ,dla których

,

dla wszystkich

Powyższe równanie definiuje podstawowa własność procesu Markowa: zachowanie się procesu nie zależy od historii; dalsza ewolucja procesu jest określona przez jego bieżący stan, a droga, jaką przebył, by dojść do tego stanu, nie jest istotna. Własność ta bywa nazywana brakiem pamięci.

Czas pobytu w dowolnym stanie ma rozkład wykładniczy z parametrem
.

Rozkład wykładniczy, jako jedyny rozkład ciągły, charakteryzuje się brakiem pamięci, tzn. prawdopodobieństwo pobytu w danym stanie przez czas t nie zależy od czasu
, który proces już w tym stanie spędził[9]:

.

Poniżej zaprezentuję przykłady systemów kolejkowych rozwiązywanych metodą analityczną. W pierwszym podrozdziale (2.2.1) przybliżę system kolejkowy z ograniczoną kolejką typu M/M/m/FIFO/m+N. W następnym - drugim (2.2.2) podrozdziale znajdziemy opis systemu kolejkowego typu M/M/2. Natomiast w ostatnim - trzecim podrozdziale (2.2.3) omówiony zostanie dwukanałowy system obsługi M/M/2. Do każdego systemu znajdzie się również przykładowe zadanie rozwiązane opisaną metodą.

1. System kolejkowy M/M/m/FIFO/m+N

Według przedstawionej w rozdziale drugim (2.1.3) symboliki A. M. Lee, akronim M/M/m/FIFO/m+N oznacza:

• wykładniczy rozkład odstępów czasu strumienia wejściowego

• wykładniczy rozkład czasu obsługi zgłoszeń,

• m - kanałów obsługi systemu,

• dyscyplina kolejki FIFO

• N - liczby miejsc w poczekalni(całkowity rozmiar systemu obsługi N=m).

System ten może znajdywać się w następujących stanach[14]:

Przy czym stany od
do
oznaczają ilość obsługiwanych w czasie zgłoszeń, a stany od
do
oznaczają, iż zajęte są wszystkie kanały obsługi i ilość „klientów” w kolejce.

Układ równań, który opisuje dynamikę takiego systemu jest układem równań Chapmana-Kołmogorowa i ma następującą postać:

Przechodząc do granicy przy
dostajemy układ algebraicznych równań opisujący stan ustalony:

Wyniki poszczególnych prawdopodobieństw, możemy przedstawić jako funkcję prawdopodobieństwa
, podstawiając
:

Prawdopodobieństwo
wyznaczyć można za pomocą warunku normalizującego, mającego postać
Po wstawieniu do niego powyższych wzorów otrzymujemy:

Wyrażenie w wewnętrznym nawiasie, które jest ciągiem geometrycznym można odpowiednio przekształcić w zależności od

Mając na uwadze powyższe wzory, można przystąpić do wyznaczania następujących charakterystyk analizowanego systemu:

Prawdopodobieństwo odmowy obsługi:

Względna zdolność obsługi systemu kolejkowego:

Bezwzględna zdolność obsługi systemu:

Średnia liczba zajętych kanałów w systemie obsługi:

Średnia liczba zgłoszeń w kolejce:

Aby obliczenia były bardziej przejrzyste, podstawmy
co w rezultacie daje:

Można jeszcze bardziej uprościć powyższy wzór gdy a = 1, wtedy mamy:

Jednak, jeśli
można zauważyć, że wyrażenie we wzorze ogólnym w nawiasie jest pochodną ciągu geometrycznego
Wobec tego:

Po podstawieniu do wzoru ogólnego otrzymanego wyniku, mamy:

Średnią liczbę zgłoszeń w systemie wyznaczamy ze wzoru:

Pamiętając jeszcze należy o uwzględnieniu odpowiedniego przypadku w zależności od wartości

Średni czas oczekiwania zgłoszenia w poczekalni wyznaczamy korzystając z pierwszej formuły Little'a:

W zależności od p wyprowadzamy z powyższego wzoru:

Średni czas przebywania zgłoszenia w systemie obsługi:

Natomiast liczba wolnych kanałów obsługi:

W następnym podrozdziale przedstawię wykorzystanie podanych wzorów.

Przykład do systemu kolejkowego M/M/m/FIFO/m+N:

Przykładem powyższego typu kolejki będzie schemat działania zakładu fryzjerskiego. Nowo przybyli klienci (strumień wejść) będą się pojawiać według rozkładu Poisson'a o parametrze λ równej 12. Zakład ten posiada czterech pracowników(4 kanały obsługi), z których każdy może obsługiwać w jednej chwili maksymalnie jednego klienta. Czas obsługi klienta(obsługa systemu) podlega rozkładowi wykładniczemu o średniej wartości
. W poczekalni dla klientów oczekujących na strzyżenie(kolejka) jest sześć foteli i są oni obsługiwani w kolejności pierwszego przybycia. W rezultacie mamy następujące dane:

• 
  przybyć na jednostkę czasu (przyjmijmy tu jedną godzinę),

• 
  klientów na godzinę,

• 
  pracowników(fryzjerów),

• 
  miejsc w poczekalni(kolejce).

Możemy to również przedstawić jako symbol M/M/4/FIFO/6.

Rozwiązanie:

Pierwszym krokiem jest obliczenie prawdopodobieństwo ustalenia się stanu braki klientów:

.

Dalej wyznaczamy prawdopodobieństwo odmowy obsługi nowoprzybyłego klienta:

.

Względna zdolność obsługi systemu czyli średnia liczba klientów obsłużonych w jednostce czasu do średniej liczby klientów przybyłych w tym czasie do systemu jest następująca:

.

Bezwzględna zdolność obsługi systemu czyli średnia liczba klientów obsłużonych w jednostce czasu wynosi:

.

Średnia liczba zajętych kanałów obsługi wynosi:

.

Średnia liczba klientów w kolejce wynosi:

.

Średnia łączna liczba klientów w systemie wynosi:

.

Średni czas przebywania klienta w kolejce wynosi:

.

Średni czas przebywania klienta w całym systemie:

.

Dodatkowo możemy oznaczyć r jako średni zysk idący z obsłużenia jednego klienta, oraz c jako wynagrodzenie jednego pracownika w określonej jednostce czasu, zatem łączny dochód na godzinę w zakładzie określany będzie wzorem:

1. System kolejkowy M/M/1

Rys. 2.4 Model systemu kolejkowego M/M/1

Symbol M/M/1 jest jednym z najczęściej obsługiwanych systemów jednokanałowych. Według angielskiego matematyka i statystyka D. Kendall'a oznacza on, że klienci nadchodzą do systemu obsługi według rozkładowi Poisson'a oraz czas obsługi jest zobrazowany rozkładem wykładniczym. Załóżmy też, że wskaźnik obsługi jest zależny od liczby zgłoszeń oczekujących w kolejce na obsługę.

W poniższych obliczeniach użyte będą następujące oznaczenia i wzory, które przedstawię według [13]:

• 
  - średni strumień zgłoszeń,

• 
  - średni czas między zgłoszeniami,

• 
  - średni wskaźnik obsługi,

• 
  - średni czas obsługi jednego zgłoszenia.

Prawdopodobieństwo, iż punkt obsługi jest zajęty (współczynnik obciążenia systemu) wynosi
. Jeśli stosunek jest większy od 1 ,wtedy kolejka jest nieskończona.

Prawdopodobieństwo, iż w systemie przebywa n klientów wynosi:

Prawdopodobieństwo, iż w systemie nie ma żadnego klienta wynosi:

.

Średnia liczba klientów w systemie wynosi:

.

Średnia liczba klientów w kolejce wynosi:

.

Średni czas przebywania klienta w systemie wynosi:

.

Średni czas przebywania klienta w kolejce wynosi:

.

Do wykorzystania wyżej wymienionych wzorów przedstawię poniższy przykład.

Przykład do systemu kolejkowego M/M/1:

Centrala telefoniczna przyjmuje zgłoszenia w rozkładzie Poisson'a ze średnią przerwą między dwoma połączeniami wynoszącą 12 minut. Średni czas trwania rozmowy wynosi 4 minuty i odpowiada rozkładowi wykładniczemu. Określ podstawowe parametry systemu[7].

Rozwiązanie:

Pierwszym krokiem rozwiązania jest obliczenie λ oraz μ z średnich czasów. Wobec tego:

.

Analogicznie wyznaczamy μ:

.

Współczynnik obciążenia systemu wynosi:

.

Średnia liczba klientów(rozmów) w systemie wynosi:

.

Średnia długość kolejki wynosi (średnia liczba połączeń, które oczekują na realizacje) :

.

Średni czas przebywania klienta w systemie(oczekiwania na połączenie oraz rozmowę) :

.

Średni czas oczekiwania na obsługę(oczekiwania na połączenie) wynosi:

.

1. System kolejkowy M/M/2

Rys.2.5 Model systemu kolejkowego M/M/2

Akronim M/M/2 oznacza dwukanałowy system obsługi, który jest przykładem symboliki M/M/m/FIFO/inf zgodnie z klasyfikacją D.Kendall'a. Ów główny symbol zostanie najpierw omówiony na wzorach[6] aby następnie przejść z nich do konkretnego przykładu jakim będzie system M/M/2. Zatem symbol M/M/m/FIFO/inf oznacza:

• strumień wejściowy jest opisany według rozkładu Poisson'a,

• czas obsługi jest rozkładem wykładniczym,

• system m-kanałowy(w naszym późniejszym przykładzie będzie to system dwukanałowy),

• dyscyplina kolejki FIFO(do systemu najpierw idzie zgłoszenie oczekujące najdłużej),

• kolejka jest nieograniczona.

System ten może znajdować się w następujących stanach[15]:

,

gdzie:

oznacza, iż w systemie jest j zgłoszeń a
.

Natomiast stany bez kolejki to od
do
, a stany z kolejką od
do
.

Układ równań różniczkowych Chapmana-Kołmogorow'a(opisujący dynamikę takiego systemu) ma postać następującą:

Przy warunkach początkowych:

Prawdopodobieństwo uzyskania następujących stanów systemu wynosi:

gdzie:
.

Prawdopodobieństwo, iż s kanałów jest zajętych wynosi:

Prawdopodobieństwo, iż długość kolejki jest r (j=m+r) wynosi:

Prawdopodobieństwo, że zajęte są wszystkie kanały (r=0) wynosi:

Średnia liczba zgłoszeń oczekujących w poczekalni na obsługę wynosi:

Średnia ilość zgłoszeń w systemie, czyli w poczekalni oraz w czasie obsługi wynosi:

gdzie:

- jest to średnia liczba klientów w systemie(w kolejce i w czasie obsługi),

- jest to średnia liczba zgłoszeń w czasie obsługi.

Średni czas oczekiwania zgłoszenia w poczekalni wynosi:

Średni czas pobytu zgłoszenia w systemie wynosi:

Poniżej przedstawię zastosowanie przedstawionych wyżej wzorów na przykładzie dwukanałowego systemu obsługi M/M/2.

Przykład do systemu kolejkowego M/M/2:

W „Wyższej Szkole Informatyki i Zarządzania” trwa rekrutacja nowych pracowników. Rozmowę kwalifikacyjną przeprowadza dziekan oraz prodziekan uczelni, każdy osobno. Kandydaci przyjmowani są według kolejności przybycia. Liczba miejsc w poczekalni jest nieograniczona. Średni czas rozmowy kandydata z prowadzącym trwa 5 minut, a co 10 minut przychodzi nowy kandydat.

Rozwiązanie:

Pierwszą czynność jaką zrobimy będzie wyznaczenie prawdopodobieństwa
, że wszystkie kanały obsługi są zajęte(czyli, że dziekan oraz prodziekan aktualnie przeprowadzają rozmowę z ewentualnymi przyszłymi pracownikami).Do tego zadania potrzebna jest nam wartość parametru
. W tym celu obliczymy intensywność strumienia zgłoszeń (
) oraz średnią intensywność obsługi (
). Wobec tego:

oraz analogicznie

Następnie obliczamy p:

W takim razie prawdopodobieństwo, że dwa kanały są zajęte wynosi:

Średnia liczba klientów oczekujących w kolejce(kandydatów na rozmowę), wynosi:

Średnia liczba obsługiwanych klientów(kandydatów) wynosi:

Średni czas oczekiwania przez klientów na obsługę(kandydatów na rozmowę) można wyliczyć korzystając z zależności:

.

oraz mając na uwadze to, że:

.

uzyskujemy:

.

Prawdopodobieństwo, że w danej chwili dwa kanały są zajęte (w tej samej chwili dziekan i promotor przeprowadzają rozmowę rekrutacyjną) wynosi:

1. Identyfikacja problemu

Naturalnym uzupełnienie wyżej omawianych modeli analitycznych są modele symulacyjne. Dzięki szybkiemu rozwojowi informatyki, szczególnej istotności nabierają symulacyjne metody analizy systemów kolejkowych. Jest to metoda, która stanowi najbardziej efektywny sposób analizy złożonych wielokanałowych systemów obsługi przy dowolnie wprowadzonych strumieniach wejściowych zgłoszeń i funkcjach rozkładów czasu obsługi. Istotnym atrybutem ich jest odzwierciedlenie związków, relacji oraz zachowań i ich cech w rzeczywistości do algorytmów sterujących w zamodelowanym programie. W niniejszej symulacji zdarzenia te odtwarzają zachowania zachodzące w sieci kolejkowej. Elementarnym celem symulacji teorii kolejek jest opracowanie procesu obsługi systemu, optymalnej struktury i organizacji kolejki. Z punktu widzenia klienta systemu należy wypracować wskazania orzeczenia sposobu użytkowania systemu obsługi, z kolei zarządzający systemem powinien określić warunki najbardziej efektowne jego wykorzystania[1].

1. Cel i zalety symulacji

Zasadniczym celem symulacji komputerowej jest odtworzenie przebiegu badanego procesu za pomocą zbudowanego algorytmu. W zamierzeniu program komputerowy powinien ułatwić zrozumienia zasad modelowanego systemu.

Główne zalety symulacji komputerowej są następujące[8]:

• Estetyczność modelu, czyli łatwość wprowadzania zmian w modelu symulowanego procesu,

• Łatwość wprowadzania różnych losowych decyzji, jakim w naszym przypadku jest strumień zgłoszeń oraz obsługa, czy też losowanie kanału,

• Stosunkowo niewielki koszt przygotowania symulacji,

• Wiarygodność symulowanych wyników,

• Symulacja zachowania przy różnych warunkach,

• Powtarzalność eksperymentów

• Krótki czas symulacji.

1. Model symulacyjny

Jak już wspomniałem symulacja komputerowa procesu musi być odzwierciedleniem procesu rzeczywistego od samego początku do końca. Symulacja rozpoczyna się od wprowadzenia i zapisania danych, jeśli są poprawne. Po wprowadzeniu danych uruchamiamy symulację, w tym czasie dokonywane są obliczenia. Ostatnim elementem jest pokazanie wyników zasymulowanych danych. Ogólny schemat symulatora przedstawię na przykładzie[9]:

Rys. 2.6 Schemat ogólny programu symulacyjnego

Początkiem procesu jest stworzenie obiektu zgłoszenie(klienta), który wchodzi do systemu w określonym czasie(strumień zgłoszeń według rozkładowi Poisson'a) dzięki generatorowi liczb pseudolosowych. Pierwszemu zgłoszeniu zawsze towarzyszy losowanie kanału obsługi, gdyż oba kanały wtedy są puste. Czas pobytu w systemie jest również generowany i opisany jest rozkładem wykładniczym. W tym czasie zbierana jest statystyka czasu oczekiwania na obsługę w kolejce, czas pobytu w systemie(generowany według rozkładu wykładniczego), czas wyjścia z systemu. Daje to nam informacje czy następne zgłoszenie stoi w kolejce, a jeśli tak to taka jest długość tej kolejki. Jeśli w systemie jest jeden kanał obsługi wolny, wtedy zgłoszenie które w tym czasie przybędzie do systemu podąża właśnie do tego kanału. Natomiast w sytuacji kiedy oba kanały systemu obsługi są zajęte, zgłoszenie pojawiające się w takim stanie systemu czeka w kolejce(poczekalni) aż zwolni się miejsce w którymś z kanałów i wtedy tam zostanie obsłużone. Jest to logiczna reakcja, gdyż porównując model stacji benzynowej z dwoma punktami tankowania, klient stojąc w kolejce i czekając aż się zwolni miejsce, wjedzie tam gdzie najszybciej będzie mógł zatankować.

3. ALGORYTM ROZWIĄZANIA PROBLEMU

Na podstawie przeprowadzonej analizy systemów kolejkowych i metod symulacji można zaproponować następujący algorytm symulacyjny systemu M/M/2 przedstawiony na rysunku 3.1 a,b,c:

Rys. 3.1a Schemat blokowy algorytmu symulatora M/M/2

Rys. 3.1b Schemat blokowy algorytmu symulatora M/M/2

Rys. 3.1c Schemat blokowy algorytmu symulatora M/M/2

4. PROJEKT SYMULATORA SYSTEMU M/M/2

Celem niniejszej pracy było zbudowanie Komputerowego Symulatora Systemu M/M/2. Do napisania symulatora zastosowałem pakiet programistyczny Borland C++ Builder 6. Program pracuje w 32 bitowym środowisku Windows. Komputerowy Symulator Systemu M/M/2 został opracowany w oparciu o założenia algorytmu z rozdziału trzeciego.

Konstruowanie symulatora składało się z kilku etapów. Pierwszym etapem było stworzenie jądra symulatora, wykorzystującego podany algorytm. Jądro te zostało zawarte w pliku glowny.cpp, w którym funkcja symuluj( ) odpowiada za cały proces symulacji oraz przechowywanie w tablicach obiektów i manipulowanie danymi. Dodatkowo funkcja ta generuje wykresy otrzymanych wyników.

Następnym etapem było stworzenie środowiska graficznego, które zostało stworzone całkowicie od początku bez korzystania z istniejących formularzy, umożliwiającego:

• łatwą i prostą do opanowania realizację procesu( tzw. przyjazny interfejs),

• wprowadzenie danych symulacyjnych i systemowych,

• przeprowadzenie symulacji,

• analizę zachowania każdego zgłoszenia z osobna w tabeli wyników dla jednej symulacji,

• sprawdzenie średnich wyników każdego zgłoszenia w tabeli średnich wyników w zależności od liczby symulacji(iteracji),

• porównanie średnich czasów oraz długości kolejki dla dwóch kanałów,

• zobrazowanie na wykresach powstałych wyników symulacji,

• zapisanie zasymulowanych wyników oraz wykresów do pliku,

• wczytanie z pliku zasymulowanych wcześniej i zapisanych danych i wyników wraz z wykresami,

• zmiany języka programu.

Poniżej na rysunku 4.1 przedstawię schemat blokowy działania symulatora komputerowego.

Rys. 4.1 Ogólny schemat działania Komputerowego Symulatora Systemu M/M/2

1. Prezentacja programu

Rys. 4.2 Okno główne aplikacji

Interfejs symulatora został zaprojektowany na wzór standartowych aplikacji Windows. Posiada on istotne dla tego typu programów: menu główne aplikacji i pasek narzędzi, czyli niejaki skrót zarządzania aplikacją oraz dodatkowymi opcjami. Zakładki w projekcie umożliwiają szybkie przemieszczanie się między częściami symulatora takimi jak wprowadzanie danych a symulacją i wynikami oraz wykresami. Pasek stanu symulacji pokazuje bieżący stan realizacji symulowanego procesu. Dość istotną właściwość ma też przycisk Zamknij, umożliwiający wyjście z programu, który „pyta się” na wszelki wypadek o zapisanie projektu, jeśli go wcześniej nie zapisaliśmy(Rys. 4.1.3) oraz czy aby na pewno zamknąć aplikację(Rys. 4.1.4).

Rys. 4.3 Komunikat o nie zapisanym projekcie

Rys. 4.4 Komunikat zamknięcia programu

1. Menu Projekt

Rys. 4.5 Zawartość menu Projekt

Menu Plik zawiera główne opcje związane z programem. Opcja Wczytaj umożliwia odczyt z pliku zapisanych wcześniej danych bądź danych z wynikami oraz możliwość ich następnej symulacji. Do zapisania tych danych służy podmenu Zapisz. Po „kliknięciu” na ostatni przycisk w menu Projekt - Zapisz, zamykamy całkowicie program, opcja ta ma również podobną właściwość jak ikona Zamknij w głównym oknie symulatora. Dodatkowo zapisane są skróty klawiszowe poszczególnych opcji.

2. Menu Dane

Rys. 4.6 Zawartość menu Dane

Menu Plik daje możliwość przemieszczania się między zakładkami kolejnych kroków symulacji. Opcje te pozwalają nam na przykład wrócić i zmienić dane do symulacji. Znaczek „fajki” przed nazwą podmenu informuje, że jesteśmy aktualnie na pozycji danej zakładki.

3. Menu Symulacja

Rys. 4.7 Zawartość menu Symulacja

Menu Symulacja ma tylko jedno podmenu startu symulacji. Jest to wygodna opcja, która pozwala bez przechodzenia w głównym oknie na zakładkę Symulacja rozpocząć proces symulacyjny. Skrótem klawiszowym jest Ctr+S.

4. Menu Wyniki

Rys. 4.8 Zawartość menu Wyniki

Najważniejszym punktem po wykonaniu symulacji są wyniki. Opcja pierwsza pozwala nam przejść do zakładki Wyniki w której znajduję się następna „podzakładka” rezultatów kolejnych zgłoszeń dla jednej symulacji - Tabela wyników dla jednej symulacji. Analogicznie(tak jak w opisie na Rys.4.8) następne opcje pozwalają na przejście do zakładek gdzie możemy zobaczyć wyniki dla zasymulowanych danych.

5. Menu Wykresy

Rys. 4.9 Zawartość menu Wykresy

Kolejne menu Wykresy tak jak w przypadku wyżej opisanych menu pozwala nam przejść w szybki sposób do interesujących nas zakładek, tym razem z wykresami. Pierwsze „submenu” Dla symulacji zawiera opcje przejścia do wykresów dla symulacji (Rys. 4.9): wykres długości kolejki, czasu oczekiwania i czasu obsługi. Identyczne również opcje posiada drugie „submenu” Dla zgłoszeń, z których możemy przejść do zakładek z wykresami dla kolejnych zgłoszeń.

6. Menu Opcje

Rys. 4.10 Zawartość menu Opcje

Dzięki tych opcji menu(Rys. 4.10) mamy możliwość zmiany języka aplikacji na język angielski i z powrotem na polski. Symbol „fajki” przed nazwą informuje nas jaki jest obecnie język aplikacji. Ponadto do każdej z tych alternatyw istnieje skrót klawiszowy.

7. Menu About

Rys. 4.11 Zawartość menu About

Ostatnie menu About zawiera tylko jedną opcję O mnie..., otwiera okno w którym znajduje się wzmianka o autorze i projekcie. Skrótem tego podmenu jest Ctrl+M.

8. Pasek narzędzi

Rys 4.12 Pasek narzędzi

Objaśnienie ikon:

• Otwórz - wczytuje dane z pliku,

• Zapisz - zapisuje dane do pliku,

• Symuluj - symulacja wprowadzonych danych,

• Tabela 1 - tabela wyników dla jedne symulacji,

• Tabela 2 - tabela wyników kolejnych symulacji,

• Wykresy 1 - wykresy dla symulacji,

• Wykresy 2 - wykresy dla zgłoszeń,

• O mnie - okno z informacją o projekcie.

1. Wprowadzanie danych

Symulator komputerowy systemu M/M/2 umożliwia wprowadzenie własnych danych za pomocą klawiatury czy też myszki, oraz po przez wczytanie danych z pliku. Wprowadzanie danych jest oczywiście ograniczone gdyż wpisując zbyt dużą liczbę musielibyśmy długo czekać albo mieć bardzo szybki komputer, oraz liczba zgłoszeń równa zero jest raczej nie do zasymulowania. Poniżej przedstawię sposoby wprowadzania danych do symulacji.

1. Ręczne wprowadzanie danych

Rys. 4.11 Pierwszy etap wprowadzania danych(Dane Symulacyjne)

Już po uruchomieniu symulatora bez zbędnych powitań znajdujemy się w pierwszym etapie wprowadzania danych symulacyjnych. W zakładce Dane Symulacyjne musimy ustalić dwie wartości: liczbę symulacji, czyli ilość powtórzeń symulacji(iteracji) takiego systemu oraz liczbę zgłoszeń(klientów) wchodzących do systemu. Wielkości te można ustalić dzięki zmianie wartości w polach Edit za pomocą klawiatury dochodząc tam klawiszem „Tab” lub tez lewym przyciskiem myszy, bądź zmniejszeniu lub zwiększeniu tego pola za pomocą tamtejszych strzałek przy liczbach. Poszczególne wartości mają ograniczony przedział liczbowy:

	Minimalna wartość	Maksymalna wartość
Liczba symulacji	10	1000
Liczba zgłoszeń	2	1000

W przypadku wpisania liczb poza przedziałem, zostaje wyświetlone powiadomienie o złych danych(Rys. 4.12) a wartości są automatycznie poprawiane.

Rys. 4.12 Komunikat o błędnych danych

Po wpisaniu wartości, lewym przyciskiem myszy zatwierdzamy wprowadzone wartości przyciskiem
(Zapisz). Po tym zdarzeniu ukazuje się kolejny etap wprowadzania danych, zakładka Dane Systemowe(Rys 4.13):

Rys. 4.13 Drugi etap wprowadzania danych(Dane Systemowe)

W oknie tym, wartości intensywności zgłoszeń oraz obsługi również mają następujące limity:

	Minimalna wartość	Maksymalna wartość
Intensywność zgłoszeń	1	10000
Intensywność obsługi	1	10000

2. Wczytanie danych z pliku

Wczytanie danych polega na odtworzeniu wcześniej zapisanych danych do pliku. W takim razie wystarczy „kliknąć” w ikonę
(Otwórz) na pasku narzędzi, lub z Menu Projekt wybrać opcję Wczytaj. Po tej operacji zostanie uruchomione okno umożliwiające lokalizację pliku z rozszerzeniem „*.kus” z danymi(Rys. 4.14).

Rys. 4.14 Odczyt danych z pliku

2. Przeprowadzanie symulacji

Po wprowadzeniu danych symulacyjnych oraz systemowych przechodzimy do następnej zakładki Symulacja(Rys. 4.15), w której jest możliwość sprawdzenia jeszcze przed symulacją poprawności zapisanych danych.

Rys. 4.15 Zakładka startu symulacji

Po „kliknięciu” w przycisk
(Start symulacji) następuje symulacja wprowadzonych danych. Gdy pasek stanu zaawansowania symulacji osiągnie 100% wtedy automatycznie jest przejście do zakładki Wyniki. Poniżej zaprezentuję działanie programu przy dwóch różnych danych.

1. System niedociążony

Rys. 4.16 Wprowadzone dane

Rys. 4.17 Tabela wyników dla jednej symulacji

Poniżej przedstawiam objaśnienie poszczególnych kolumn:

• lp - Liczba porządkowa kolejnych zgłoszeń symulacji,

• cz_m_zgł - jest to czas odstępu pojawienia się zgłoszeń w systemie, generowany według rozkładu Poisson'a,

• czek_1, czek2 - oznacza czas oczekiwania w kolejce zgłoszeń na obsługę dla kanału pierwszego lub drugiego,

• kolejka_1, kolejka2 - jest numerem kolejki dla zgłoszenia oczekujące na obsługę po przybyciu do systemu dla kanału pierwszego lub drugiego,

• obsł_1, obsł_2 - jest to czas obsługi zgłoszenia w systemie w kanale pierwszym lub drugim, generowany według rozkładu wykładniczego,

• l_obsł_1, l_obsł_2 - symbolizuje liczbę zgłoszeń obsłużonym w kanale pierwszym lub drugim,

• pobyt_1, pobyt_2 - określa ogólny czas pobytu w systemie dla kanału pierwszego lub drugiego, jest sumą czasu oczekiwania i czasu obsługi,

• wyjscie_1, wyjscie_2 - jest to czas wyjścia zgłoszenia z kanału pierwszego bądź drugiego, liczy się to jako sumę czasu przybycia zgłoszenia do systemu i ogólnego pobytu w systemie.

Powyższy rysunek 4.17 prezentuje wyniki kolejnych zgłoszeń tylko dla jednej symulacji. Aby rozpatrzyć średnie wyniki dla wprowadzonych 10 takich symulacji, przemieszczamy się na następna zakładkę tabela średnich wyników kolejnych symulacji (Rys. 4.18).

Rys. 4.18 Tabela średnich wyników kolejnych symulacji

Z powyższej tabeli średnich wyników(Rys. 4.18) w kolejnych zakładkach otrzymujemy:

Rys. 4.19 Średnie wyniki dla kanałów obsługi

Rys. 4.20 Graficzne wyniki

Rys. 4.21Wykres dla symulacji - długość kolejki

Rys. 4.22 Wykres dla symulacji - czas oczekiwania

Rys. 4.23 Wykres dla symulacji - czas oczekiwania

Rys. 4.24 Wykres dla zgłoszeń - długość kolejki

Rys. 4.25 Wykres dla zgłoszeń - czas oczekiwania

Rys. 4.26 Wykres dla zgłoszeń - czas obsługi

1. System obciążony

Rys. 4.27 Wprowadzone dane

Rys. 4.28 Tabela wyników dla jednej symulacji

Dla tak przyjętych danych(Rys. 4.27) przy kolejnych zgłoszeniach pojawia się kolejka. Poniżej przedstawię objaśnienie pierwszych 10 zgłoszeń:

• 1 zgłoszenie - przybycie do systemu 0,01081; wylosowanie kanału pierwszego; wyjście z systemu 0,01262,

• 2 zgłoszenie - przybycie do systemu 0,01340; wylosowanie kanału drugiego; wyjście z systemu 0,01966,

• 3 zgłoszenie - przybycie do systemu 0,01824; wejście do wolnego kanału pierwszego; wyjście z systemu 0,03723,

• 4 zgłoszenie - przybycie do systemu 0,02144; wejście do wolnego kanału drugiego; wyjście z systemu 0,03637,

• 5 zgłoszenie - przybycie do systemu 0,03136; wejście do najszybciej zwolnionego kanału drugiego; kolejka = 1; wyjście z systemu 0,04488,

• 6 zgłoszenie - przybycie do systemu 0,03233; wejście do najszybciej zwolnionego kanału pierwszego; kolejka = 2; wyjście z systemu 0,04195,

• 7 zgłoszenie - przybycie do systemu 0,03665; wejście do najszybciej zwolnionego kanału pierwszego; kolejka = 2; wyjście z systemu 0,04633,

• 8 zgłoszenie - przybycie do systemu 0,03781; wejście do najszybciej zwolnionego kanału drugiego; kolejka = 2; wyjście z systemu 0,05267,

• 9 zgłoszenie - przybycie do systemu 0,03873; wejście do najszybciej zwolnionego kanału pierwszego; kolejka = 3; wyjście z systemu 0,09547,

• 10 zgłoszenie - przybycie do systemu 0,04291; wejście do najszybciej zwolnionego kanału drugiego; kolejka = 3; wyjście z systemu 0,05662.

Rys. 4.29 Tabela średnich wyników kolejnych symulacji

Rys. 4.30 Średnie wyniki dla kanałów obsługi

Rys. 4.31 Graficzne wyniki

Rys. 4.31 Wykres dla symulacji - długość kolejki

Rys. 4.32 Wykres dla symulacji - czas oczekiwania

Rys. 4.33 Wykres dla symulacji - czas obsługi

Rys. 4.34 Wykres dla zgłoszeń - długość kolejki

Rys. 4.35 Wykres dla zgłoszeń - czas oczekiwania

Rys. 4.36 Wykres dla zgłoszeń - czas obsługi

1. Dodatkowe opcje

Dobrym uzupełnieniem symulatora komputerowego systemu M/M/2 jako aplikacji interaktywnej jest możliwość zapisania istniejącego projektu po symulacji do pliku oraz zmiany języka na inny, bardziej powszechny - angielski. Również każda aplikacja powinna mieć funkcję sprawdzenia podstawowych informacji o programie.

1. Zapisanie wyników do pliku

Aby zapisać projekt, należy z menu Projekt wybrać opcję Zapisz lub nacisnąć ikonę
(Zapisz) . Po tym działaniu otwiera nam się okno zapisu (Rys. 4.37). Aby zapisać dane do pliku należy wpisać nazwę pliku oraz „kliknąć” przycisk Zapisz.

Rys. 4.37 Zapis danych do pliku

2. Zmiana języka aplikacji

Z menu Opcje->Język po wybraniu opcji English lub użyciu skrótu klawiszowego Ctrl+E zmieniony zostaje język całej aplikacji z polskiego na angielski (Rys.4.38).

Rys. 4.38 Komputerowy Symulator Systemu M/M/2 w języku angielskim

3. Informacje o projekcie

Aby sprawdzić informacje o projekcie należy z menu About wybrać opcję O mnie... . Po tej operacji ukazuje się poniższe okno(Rys. 4.39):

Rys. 4.39 Okno z informacją o projekcie

5. ZAKOŃCZENIE

1. Podsumowanie

W niniejszej pracy zaprezentowano zagadnienia komputerowej symulacji systemu M/M/2. W opracowanym Komputerowym Symulatorze Systemu M/M/2 :

• System M/M/2 symulowany przez program posiada dwa kanały obsługi z nieograniczoną kolejką oraz zgłoszenia wchodzą według kolejki FIFO,

• Strumień zgłoszeń oraz czas obsługi generowany jest przez generatory liczb pseudolosowych w zależności od wprowadzonej
  oraz
  ,

• Większa wartość liczby symulacji pozwala uzyskać wynik bardziej dokładnych średnich wyników. Można to zauważyć już na mniejszej różnicy czasu między zgłoszeniami oraz czasem obsługi(Rys. 4.29 i 4.30),

• Tabela wyników kolejnych zgłoszeń zaprezentowana jest dla jednej symulacji oraz dla wszystkich symulacji jako średnia każdego zgłoszenia,

• Średnie wyniki dla kanałów obsługi pomagają stwierdzić wydolność obydwóch kanałów,

• Wykresy umożliwiają szybkie i intuicyjne zapoznanie się z prezentowanymi wynikami oraz ich porównanie,

• Opcja zapisania danych do pliku oraz późniejszy odczyt ich pozwoli na głębszą analizę wyników oraz wyszukanie najbardziej optymalnego rozwiązania.

1. Wnioski

Uważam, iż prawidłowe działanie Komputerowego Symulatora Systemu M/M/2 i zgodność jego parametrów z założoną tezą świadczą o poprawności zaproponowanego rozwiązania. Wynikają z tego następujące wnioski:

• Zastosowanie symulatora w procesie obsługi zgłoszeń znacznie ułatwia i skraca czas poszukiwania i testowania algorytmów sterowania obsługą,

• Wykorzystanie technik programistycznych pozwala na zaprojektowanie symulatora, który realizuje rzeczywiste zjawiska zachodzące w systemie obsługi,

• Posługując się symulatorem można przewidzieć czy wybrany wariant systemu potrafi wykonać zadania w odpowiednim czasie oraz czy poszczególne dane są dobrze dobrane,

• Sądzę, iż Komputerowy Symulator Systemu M/M/2 będzie miał zastosowanie w oficjalnym nauczaniu przynajmniej w Wyższej Szkole Informatyki i Zarządzania w Bielsku-Białej.

6. LITERATURA

Książki i publikacje

1. Filipowicz B., „Modele stochastyczne w badaniach operacyjnych”, Warszawa, 1996, str.11-33.

2. Filipowicz B., „Modelowanie i analiza sieci kolejkowych”, Kraków, 1997, str. 157-175.

3. Kałuski J., „Wykłady z systemów obsługi masowej”, WSiZ, rok akademicki 2005/2006(skrypt niepublikowany).

4. Kondratowicz L., „Modelowanie symulacyjne systemów”, Warszawa, 1978, str. 231-237.

5. Kendall D.G., „Some problems in the theory of queues”, Journal of the Royal Statisticial Society, 1951, str. 157-176.

6. Erlang A.K., „The theory of probability and telephone conversations”, Nyt. Tidsskrift Mat., 1909, str. 33-39.

7. Mischel J.i Duntemann J., „Borland C++ Builder“, Warszawa, 1997, str. 15-147.

8. Stasiewicz A., „C++ Builder. Symulacje komputerowe”, Gliwice, 2003.

Prace dyplomowe WSIiZ

9. Król B., „Symulator dwukanałowego systemu obsługi M/M/2”, Bielsko-Biała, Wyższa Szkoła Informatyki i Zarządzania, 2003.

10. Jurij T., „Systemy obsługi masowej - prezentacja internetowa”, Bielsko-Biała, Wyższa Szkoła Informatyki i Zarządzania, 2004.

11. Gacek P., „Komputerowa analiza sieci kolejek”, Bielsko-Biała, Wyższa Szkoła Informatyki i Zarządzania, 1998.

Witryny internetowe

12. Wikipedia, artykuł o teorii kolejek http://pl.wikipedia.org/wiki/Teoria_kolejek .

13. Dr. inż. Jolanty Talar - AGH Kraków, witryna o teorii kolejek, http://www.metal.agh.edu.pl/~jtalar/logistyka/pr_lin/teoria_kolejek.html .

14. Nieznany, lekcja multimedialna o systemach markowskich typu M/M/m/FIFO/m+N, http://www.bo.wieczysta.com/index.php?id=4 .

15. Nieznany, lekcja multimedialna o systemach markowskich typu M/M/m/FIFO/inf, http://www.bo.wieczysta.com/index.php?id=3 .

16. Nieznany, witryna internetowa na temat symulacji komputerowej, http://tziaja.strony.wi.ps.pl/Etapy .

17. Massachusetts Insitute of Technology, prezentacja multimedialna z jednokanałowego systemu obsługi, http://ocw.mit.edu/NR/rdonlyres/Civil-and-Environmental-Engineering/1-225JFall2002/00B66A2C-9A97-4763-A80E-960F8CFEB848/0/lec8_example.pdf .

18. Sobczyk J. - Wydział Elektroniki i Technik Informacyjnych, skrypt o rozkładzie wykładniczym i procesie Poisson'a, http://staff.elka.pw.edu.pl/~pszablow/PPSZ/w/w3.pdf .

19. Smolarek L. - Akademia Morska w Gdyny, dokument na temat symulacji jedno-kanałowych systemów obsługi masowej typu M/M/1, M/G/1,G/M/1, http://www.wsm.gdynia.pl/~leszsmol/msu/WYKLAD8.doc .

20. Dr. Jaroslav Sklenar, University of Malta, symulator komputerowy systemu M/M/1, http://staff.um.edu.mt/jskl1/simweb/simmm1.html .

21. Takashi Ohyama, symulator komputerowy systemu M/M/2., http://www.nirarebakun.com/queue/emm2.html .

7. SUMMARY

This paper highlights the problem of the two channel system of serving arrivals - the M/M/2 system. This type of system can be used at post offices, in banks, or at petrol filling stations. The most important task of the system is to minimize the waiting time and costs of service to the client. In order to achieve this task, it is important to find the optimal balance between the length of the queue and the length of service, as to ensure that profits are as high as possible.

The solution to this problem is a computer program written by me in the C++ language - a computer simulator of the M/M/2 system, which simulates the above mentioned type of situation. The M/M/2 system includes:

• Poisson arrival stream,

• time for serving arrivals is sometimes exponential,

• two service channels,

• unlimited queue for arrivals waiting for service,

• FIFO type of entry for arrivals.

In the simulator, both simulated and system data is entered. The larger the number of simulations, the more accurate the average results become. Data can be imported from files and the simulated results can be saved. The results of one simulation are presented in a table, in which every arrival is shown as well as a table of average results of the arrivals. It is also possible to view the results graphically in the format of charts and graphs.

If the user of the program is not familiar with the Polish language, there is an option to change the language to English. Thanks to this option, the simulator can be made accessible to a wider range of consumers.

4

O mnie

Wykresy 2

Wykresy 1

Tabela 2

Tabela 1

Symuluj

Zapisz

Otwórz

Informacje o programie

Język angielski

Język polski

Przejście do zakładki Wykresy dla zgłoszeń i wybranej „podzakładki”

Przejście do zakładki Wykresy dla symulacji i Czas obsługi

Przejście do zakładki Wykresy dla symulacji i Czas oczekiwania

Przejście do zakładki Wykresy dla symulacji i Długość kolejki

Przejście do zakładki Wyniki i Graficzne wyniki

Przejście do zakładki Wyniki i Średnie wyniki dla kanałów obsługi

Przejście do zakładki Wyniki i Tabela średnich wyników kolejnych symulacji

Przejście do zakładki Wyniki i Tabela wyników dla jednej symulacji

Rozpoczęcie symulacji

Przejście do zakładki Symulacja

Przejście do zakładki Dane Systemowe

Przejście do zakładki Dane Symulacyjne

Wyjście z programu

Zapis danych do pliku

Odczyt danych z pliku

Wyjście z

programu

Okno główne symulatora

Zakładki kolejnych kroków symulacji

Pasek stanu zaawansowania symulacji

Pasek narzędzi

Menu Główne

Wyjście z

systemu

Zmień język

Zapisz dane
i wyniki

Czas obsługi

Czas oczekiwania

Długość kolejki

Wykresy dla

zgłoszeń

Czas obsługi

Czas oczekiwania

Długość kolejki

Wykresy dla

symulacji

Wyniki graficzne

Wyniki średnie dla
kanałów obsługi

Tabela wyników średnich
dla kolejnych symulacji

Tabela wyników dla

jednej symulacji

Przeglądanie

wyników

Wczytaj

dane wyniki

Symulacja

Wprowadź dane

systemowe

Wprowadź dane

symulacyjne

Komputerowy Symulator

Systemu M/M/2

Licz: czas wyjścia z systemu

= czas przybycia + czas pobytu

Licz: czas pobytu w systemie = czas obsługi + czas oczekiwania

Idź do zwolnionego kanału

Licz: długość kolejki

Licz: czas oczekiwania w kolejce

= najszybszy czas wyjścia zgł. w obsłudze - czas przybycia zgł. X

NIE

2

Losuj kanał

B

Licz: czas wyjścia z systemu

= czas przybycia + czas pobytu

Licz: czas pobytu w systemie = czas obsługi

Idź do wolnego

kanału

1

TAK

Ile kanałów

jest wolnych?

Czy kanały są

zajęte?

Licz: czas między zgłoszeniami = czas przybycia zgł. X - czas przybycia zgł. X-1

Generuj czas przybycia następnego zgłoszenia X

Wyświetl

wyniki

STOP

TAK

NIE

Czy zaszły wszystkie

zgłoszenia?

B

A

A

B

Licz: czas wyjścia z systemu

= czas przybycia + czas pobytu

Licz: czas pobytu w
systemie = czas obsługi

Licz: czas wyjścia z systemu

= czas przybycia + czas pobytu

Licz: czas pobytu w
systemie = czas obsługi

Idź do wolnego kanału

Losuj kanał

TAK

NIE

Czy zgłoszenie pierwsze jest jeszcze w systemie?

Licz: czas między zgłoszeniami = czas przybycia zgł. drugiego - czas przybycia zgł. pierwszego

Generuj czas przybycia drugiego zgłoszenia

Licz: czas wyjścia z systemu

= czas przybycia + czas pobytu

Licz: czas pobytu w systemie = czas obsługi

Generuj czas obsługi

zgłoszenia

Losuj kanał

Generuj czas przybycia

pierwszego zgłoszenia

Symuluj dla

wprowadzonych danych

TAK

NIE

Czy dane

są poprawne?

Wczytaj dane
systemowe

TAK

NIE

Czy dane

są poprawne?

Wczytaj dane
symulacyjne

START

KONIEC

prezentacja
wyników

Symulacja i
dokonanie

obliczeń

kontrola
danych

Wczytaj
dane

START

μ

λ

Strumień
wyjściowy

Kanały
obsługi

m

1

Poczekalnia
(kolejka)

System kolejkowy

Strumień wejściowy

---