Immune Ant Colony Algorithm for MultiTask Scheduling Problem
ZHONG YiWen1,2, YANG JianGang1
1.College of Computer Science and Technology, Zhejiang University, Hangzhou 310027 2.College of Computer and Information, Fujian Agriculture and Forestry University, Fuzhou 350002
Abstract This paper presents an immune ant colony algorithm for multitask scheduling in parallel and distributed systems. Ant colony algorithm is used to evolve a priority list firstly, then the priority list is mapped to a schedule by a greedy strategy. In order to avoid premature stagnation, immune principle is used to preserve the diversity of the population of ants. The simulation results compared with those of genetic algorithm and list scheduling which are typical in literature, show that it produces encouraging results in both solution complexity and execution time.
[1] Wu M Y, Gajski D D. Hypertool: A Programming Aid for Message-Passing Systems. IEEE Trans on Parallel and Distributed Systems, 1990, 1(3): 330-343 [2] Shi W, Zheng W M. The Balanced Dynamic Critical Path Scheduling Algorithm of Dependent Task Graphs. Chinese Journal of Computers, 2001, 24(9): 991-997 (in Chinese) (石 威,郑纬民.相关任务图的均衡动态关键路径调度算法.计算机学报, 2001, 24(9): 991-997) [3] Zhong Y W, Yang J G. A Genetic Algorithm for Tasks Scheduling in Parallel Multiprocessor Systems. In: Proc of the 2nd International Conference on Machine Learning and Cybernetics. Xi’an, China, 2003, Ⅲ: 1785-1790 [4] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies. In: Proc of the 1st European Conference on Artificial Life. Paris, France, 1992, 134-142 [5] Colorni A, Dorigo M, Maniezzo V. An Investigation of Some Properties of an Ant Algorithm. In: Proc of the Parallel Problem Solving from Nature Conference. Brussels, Belgium, 1992, 509-520 [6] Wang X F, Zhang X J, Cao X B, et al. An Improved Genetic Algorithm Based on Immune Principle. Mini-Micro Systems, 1999, 20(2): 117-120 (in Chinese) (王煦法,张显俊,曹先彬,等.一种基于免疫原理的遗传算法.小型微型计算机系统, 1999, 20(2): 117-120) [7] Cui X X, Li M, Fang T J. Research on Population Diversity of Multi-Objective Evolutionary Algorithms Based on Immune Principle. Pattern Recognition and Artificial Intelligence, 2001, 14(3): 291-296 (in Chinese) (崔逊学,李 淼,方廷健.基于免疫原理的多目标进化算法群体多样性研究.模式识别与人工智能, 2001, 14(3): 291-296) [8] Dorigo M, Maniezzo V, Colorni A. The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Trans on Systems, Man, and Cybernetics-Part B: Cybernetics, 1996, 26(1): 29-41 [9] Stutzle T, Hoos H. Improvements on the Ant System: Introducing MAX-MIN Ant System. In: Proc of the International Conference on Artificial Neural Networks and Genetic Algorithms. Heidelberg, Germany: Springer Verlag, 1997, 245-249 [10]Bullnheimer B, Hartl R F, Strauss C. A New Rank Based Version of the Ant System: A Computational Study. Central European Journal for Operations Research and Economics, 1999, 7(1): 25-38 [11]Nakamichi Y, Arita T. Diversity Control in Ant Colony Optimization. 2004. http://www.it.bond.edu.au/publications/02TR/02-18.pdf [12]Almeida V A F, Vasconcelos I M M, Arabe J N C, Menusc D A. Using Random Task Graphs to Investigate the Potential Benefits of Heterogeneity in Parallel Systems. In: Proc of the IEEE/ACM Conference on High Performance Networking and Computing. Minneapolis, USA, 1992, 683-691
2006, Vol. 19 
