Heurystyczne algorytmy szeregowania wiadomości z terminami dostarczeń

Abstract

Artykuł 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. Określono wymagania czasu rzeczywistego adekwatne dla komunikacji asynchronicznej. Wskazano szkic dowodu na nieistnienie dokładnego algorytmu optymalizacji kosztu całkowitego sigmawjCj dla omawianego zagadnienia. Zaproponowano algorytmy heurystyczne, opierające się na sortowaniu bąbelkowym, przesuwaniem małych wiadomości do przodu kolejki oraz zamianie z szacowaniem potencjalnego zysku czy też drogi. Wykonano aplikację symulującą losowe zestawy danych i dokonującą optymalizacji proponowanymi algorytmami. Dla porównania przedstawiono wyniki algorytmu RT STD oraz przeglądu zupełnego. 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 sigmawjCj for discussed problem by it's transformation into the knapsack problem is proved. Heuristic algorithms based on bubble sorting, moving the small message into the front of the queue and changing with assessment of the potential gain or distance are proposed. An application simulating the random data sets and optimizing using methods previously described, is created. RT STD and permutations results are presented to compare. Achieved results are discussed.