Czasopismo
2011
|
R. 108, z. 4-M/1
|
135-140
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Application of ant colony systems in solving of task scheduling problem
Języki publikacji
Abstrakty
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.
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.
Czasopismo
Rocznik
Tom
Strony
135-140
Opis fizyczny
Bibliogr. 8 poz.,Wz., wykr.,
Twórcy
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BGPK-3590-3898