Implementation of ant colony system heuristics in the task scheduling problem

• Autorzy: Filo, G.
• Języki publikacji: EN

Abstrakty

EN

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

EN

ant colony systems; optimization; task scheduling problem

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2011
• Tom: Vol. 36, No. 3-4
• Strony: 191-205
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Filo, G.

• Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics,

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).