Zastosowanie algorytmów mrówkowych w rozwiązaniu problemu szeregowania zadań

• Autorzy: Filo G.

Warianty tytułu

EN

Application of ant colony systems in solving of task scheduling problem

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono propozycję rozwiązania problemu szeregowania zadań TSP (ang. Task Scheduling Problem) określonego za pomocą skierowanego grafu w warunkach ograniczonych zasobów za pomocą algorytmów mrówkowych ACS (ang. Ant Colony System). Zaprojektowano i wykonano własne oprogramowanie w środowisku RAD C++ Turbo Explorer. Oprogramowanie posłużyło do przeprowadzenia wielu badań pozwalających na dobór parametrów ACS w celu rozwiązania problemu TSP. Wyniki wskazują, że zastosowanie ACS stanowi korzystną alternatywę dla używanych algorytmów suboptymalnych typu wielomianowego, jak algorytm Hu lub LPT.

EN

In this paper is presented proposal of solving the task scheduling problem (TSP) given by directed graph, under limited resources condition using the ant colony system (ACS). The own software in C++ Turbo Explorer rapid application development environment was designed and developed. The software was used to carry out series of simulations, what allowed to choose the best parameters of the ACS in solving of the TSP problem. The results indicate, that using of the ACS is an advantageous option to commonly used suboptimal polynomial algorithms, like Hu or LPT.

Słowa kluczowe

PL

algorytmy mrówkowe; optymalizacja; szeregowanie zadań

EN

ant colony systems; optimization; task scheduling

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Mechanika
• Rocznik: 2011
• Tom: R. 108, z. 4-M/1
• Strony: 135--140
• Opis fizyczny: Bibliogr. 8 poz.,Wz., wykr.,

Twórcy

autor

Filo G.

• Instytut Informatyki Stosowanej, Wydział Mechaniczny, Politechnika Krakowska

Bibliografia

• [1] Anguliar J., A General Ant Colony Model to solve Combinatorial Optimization Problems, Revista Colombiana de Computacion, Vol. 2, No. 1, 2001.
• [2] Coffman E., Teoria szeregowania zadań, WNT, Warszawa, 1980.
• [3] Corne D., Dorigo M., Glove F., New ideas in Optimization, McGraw Hill, 1999.
• [4] Dorigo M., Stützle T., Ant colony optimization, MIT Press, USA, 2004.
• [5] Grzymkowski R. i inni, Wybrane algorytmy optymalizacji. Algorytmy genetyczne, Algorytmy mrówkowe, PKJS, 2008.
• [6] Sinnen O., Sousa L., On Task Scheduling Accuracy: Evaluation Methodology and Results, The Journal of Supercomputing, Vol. 27, No. 2, Kluwer 2004.
• [7] Trojanowski K., Metaheurystyki praktycznie, Wydawnictwo Wyższej Szkoły Informatyki i Zarządzania, Warszawa 2003.
• [8] Serwis zawierający przykładowe grafy zadań (kasahara.elec.waseda.ac.jp/schedule/index.html).