Discrete Particle Swarm Optimization Algorithm for Independent Task Assignment Problem
ZHONG YiWen1,2, YANG JianGang2
1.College of Computer and Information, Fujian Agriculture and Forestry University, Fuzhou 350002 2.College of Computer Science and Technology, Zhejiang University, Hangzhou 310027
Abstract A discrete particle swarm optimization algorithm is designed to tackle the independent task assignment problem in heterogeneous computing systems. Based on the characteristics of discrete variable, particle’s position, velocity and their operation rules are redefined in this paper. In order to restrain premature stagnation, individual diversity of particle and microdiversity of particle swarm are defined. A repulsion operator is designed to keep the diversity of particle swarm, and a learning operator is defined to improve intensification ability of the algorithm. The proposed algorithm gets good balance between exploration and exploitation using those operators. The simulation results show the proposed algorithm has good performance comparing with a hybrid genetic algorithm and a list scheduling, both typical from the literature.
[1] Kennedy J, Eberhart R. Particle Swarm Optimization. In: Proc of the IEEE International Conference on Neural Networks. Perth, Australia, 1995, 1942-1948 [2] Clerc M. Discrete Particle Swarm Optimization. In: Onwubolu G C, Babu B V, eds. New Optimization Techniques in Engineering. Heidelberg, Germany: Springer-Verlag, 2004, 219-240 [3] Cagnina L, Esquivel S, Gallard R. Particle Swarm Optimization for Sequencing Problems: A Case Study. In: Proc of the Congress on Evolutionary Computation. Oregon, Portland, 2004, Ⅰ: 536-541 [4] Salman A, Ahmad I, Al-Madani S. Particle Swarm Optimization for Task Assignment Problem. Microprocessors and Microsystems, 2002, 26(8): 363-371 [5] Li N, Zou T, Sun D B. Particle Swarm Optimization for Vehicle Routing Problem with Time Windows. System Engineering-Theory and Practice, 2004, 24(4): 130-135 (in Chinese) (李 宁, 邹 彤, 孙德宝. 带时间窗车辆路径问题的粒子群算法.系统工程理论与实践, 2004, 24(4): 130-135) [6] Braun T D, Siegel H J, Beck N, et al. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing, 2001, 61(6): 810-837 [7] Wu M Y, Shu W, Zhang H. Segmented Min-Min: A Static Mapping Algorithm for Meta-Tasks on Heterogeneous Computing Systems. In: Proc of the 9th IEEE Heterogeneous Computing Workshop. Cancun, Mexico, 2000, 375-385 [8] Zhong Y W, Yang J G. A Hybrid Genetic Algorithm for Independent Tasks Scheduling in Heterogeneous Computing Environments. Journal of Beijing University of Aeronautics and Astronautics, 2004, 30(11): 1080-1083 (in Chinese) (钟一文, 杨建刚. 异构计算系统中独立任务调度的混合遗传算法. 北京航空航天大学学报, 2004, 30 (11): 1080-1083)
2006, Vol. 19 
