Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Heuristic algorithms of optimization of cost in message queuing systems
Języki publikacji
Abstrakty
Artykuł ten przedstawia problem optymalizacji komunikacji asynchronicznej w kontekście szeregowania wiadomości w systemach wiadomości kolejkowanych (MQ). Sporządzono model systemu i przedstawiono problem optymalnej komunikacji. Szczególną uwagą objęto zagadnienie podziału na pakiety sieciowe strumienia przesyłanych danych. Wyznaczono czas oczekiwania na wiadomość, uwzględniający wymienione zjawisko. Dowiedziono nieistnienia dokładnego algorytmu optymalizacji kosztu całkowitego ∑wjCj, dla omawianego zagadnienia poprzez jego transformację do problemu plecakowego. Zaproponowano algorytmy heurystyczne, opierające się na sortowaniu bąbelkowym, wstępnym sortowaniu metodą WSPT, przesuwaniem małych wiadomości do przodu kolejki oraz zamianie z szacowaniem potencjalnego zysku. Wykonano aplikację symulującą losowe zestawy danych i dokonującą optymalizacji proponowanymi algorytmami. Dla porównania przedstawiono wyniki WSPT i przeglądu zupełnego (o ile to było możliwe). Otrzymane wyniki zinterpretowano.
The article presents the problem of optimizing the asynchronous communication in message queuing systems. A system model is created and as well as the question of optimal communication discussed. A special importance is attached to the problem of dividing the stream of transmitted data into web packets. The time of awaiting for the message taking the occurrence mentioned above into consideration is stated. Lack of precise algorithm for optimizing the total cost ∑wjCj for discussed problem by it's transformation into the knapsack problem is proved. Heuristic algorithms based on bubble sorting, preliminary WSPT (Weighted Shortest Processing Time) sorting, moving the small message into the front of the queue and changing with assessment of the potential gain are proposed. An application simulating the random data sets and optimizing using methods previously described, is created. WSPT and permutations results (when possible) are presented to compare. Achieved results are discussed.
Słowa kluczowe
Wydawca
Rocznik
Tom
Strony
221--227
Opis fizyczny
Bibliogr. 2 poz., tab.
Twórcy
autor
- Laboratorium Informatyki Katedry Automatyki, Akademia Górniczo-Hutnicza w Krakowie
Bibliografia
- [1] Sysło M.M., Narsingh D., Kowalik J.S.: Algorytmy optymalizacji dyskretnej z programami w języku Pascal. Warszawa, PWN 1993, rozdział 4.2.5
- [2] Piórkowski A.: Szeregowanie wiadomości z uwzględnieniem podziału na pakiety sieciowe w systemach wiadomości kolejkowanych, [w:] Materiały Konferencyjne IX Konferencji Systemów Czasu Rzeczywistego, Ustroń 2002
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH1-0014-0034