Czasopismo
2011
|
Vol. 36, No. 3-4
|
191-205
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
The task scheduling problem (TSP) in general is a NP-complete combinatorial optimization problem. In practice, it can be applied in informatics, economics, production planning, logistics etc. This paper presents proposal of solving the TSP problem given by directed graph using the ant colony system (ACS) heuristic algorithm under the limited resources condition. The own software was designed using UML and implemented in C++. It was used to carry out simulations in order to find optimal values of ACS parameters, as a pheromone evaporation coefficient, probability of node selection by roulette algorithm, population size etc. Obtained values of parameters were next used in order to find solutions of TSP various sizes graphs. The results indicate, that using of the ACS is advantageous in relation to commonly used suboptimal polynomial algorithms, like Hu or LPT.
Słowa kluczowe
Rocznik
Tom
Strony
191-205
Opis fizyczny
Bibliogr. 10 poz.
Twórcy
autor
- Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics, filo@mech.pk.edu.pl
Bibliografia
- [1] Anguliar J.: A General Ant Colony Model to solve Combinatorial Optimization Problems, Revista Colombiana de Computation, v2, 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] Orłowski C. (red.): Zarządzanie technologiami informatycznymi : stan i perspektywy rozwoju, chapter: Systemy agentowe - cechy, zastosowanie oraz przegląd narzędzi do ich tworzenia, Pomorskie Wydawnictwo Naukowo-Techniczne, Gdańsk, 2006.
- [7] Kowalczuk Z., Orłowski C.: Design of knowledge-based systems in environmental engineering, Cybernetics and Systems, vol. 35 nr 5-6, p.p. 487-498, 2004.
- [8] Sinnen O., Sousa L.: On Task Scheduling Accuracy: Evaluation Methodology and Results, The Journal of Supercomputing, v. 27 no. 2, Kluwer, 2004.
- [9] Trojanowski K.: Metaheurystyki praktycznie, Wydawnictwo Wyższej Szkoły Informatyki i Zarządzania, Warszawa, 2003.
- [10] http://www.kasahara.elec.waseda.ac.jp/schedule/index.html (internet service which contains example task graphs).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BPP2-0019-0063