Email this article 
Open Access
Subscription or Fee Access
A New Approach for Task Scheduling Using Elite Particle Swarm Optimization
Abstract
This paper presents a modified approach for task assignment problem or multiprocessor scheduling using Elite Particle Swarm Optimization. Particle Swarm Optimization (PSO) is a population based heuristic optimization technique. The concept of elitism is combined with the Particle Swarm Optimization which yields promising result when compared to Normal PSO. Elitism is the process of preserving the best solutions for computation to achieve near optimal solutions. The strategy of replacing the worst string of the new population with the best string of the current population is adopted in this method. Particle Swarm Optimization Algorithms with this strategy are referred as Elite Particle Swarm Optimization Algorithm or EPSO. Elitism can rapidly increase the performance of PSO, because it prevents losing the best found solution to date.Elitism is also combined with mutation to prevent the algorithm being stuck at local optima. The result show that the Particle Swarm Optimization with elitism and mutation performs better than the normal Particle Swarm Optimization with dynamically varying inertia method.
Keywords
References
J. Kennedy and Russell C. Eberhart, “Swarm Intelligence”, Morgan-Kaufmann, 2001, pp 337-342.
Peng-Yeng Yin, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang, “A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems”, Computer Standards & Interfaces ,Vol.28, 2006, pp. 441-450.
Virginia Mary Lo, “Heuristic algorithms for task assignment in distributed systems”, IEEE Transactions on Computers, Vol. 37, No. 11,1998, pp. 1384– 1397.
Abdelmageed Elsadek, B. Earl Wells, “A Heuristic model for task allocation in heterogeneous distributed computing systems”, The International Journal of Computers and Their Applications, Vol. 6, No.1, 1999,pp.1- 36.
M. Fatih Taşgetiren & Yun-Chia Liang, “A Binary Particle Swarm Optimization Algorithm for Lot Sizing Problem”, Journal of Economic and Social Research, Vol.5, No.2, 2003, pp. 1-20.
Tzu-Chiang Chiang , Po-Yin Chang, and Yueh-Min Huang, “Multi-Processor Tasks with Resource and Timing Constraints Using Particle Swarm Optimization”, IJCSNS International Journal of Computer Science and Network Security, Vol.6, No.4, 2006, pp. 71-77.
K.E. Parsopoulos, M.N. Vrahatis, “Recent approaches to global optimization problems through particle swarm optimization”, Natural Computing , Vol.1, 2002, pp. 235 – 306.
Chen Ai-ling, YANG Gen-ke, Wu Zhi-ming, “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem”, Journal of Zhejiang University Vol.7, No.4, 2006, pp.607-614.
Ruey-Maw Chen, Yueh-Min Huang, ”Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Techniques, Journal of Neural Computing and Applications, Vol.10, No.1, 2001, pp.12 – 21.
Dar-Tzen Peng, Kang G. Shin, Tarek F. Abdelzaher, “ Assignment and Scheduling Communicating Periodic Tasks in Distributed Real-Time Systems”, IEEE Transactions On Software Engineering, Vol. 23, No. 12, 1997, pp.745 – 748.
Rui Mendes, James Kennedy and José Neves, “The Fully Informed Particle Swarm: Simpler, Maybe Better”, IEEE Transactions of Evolutionary Computation, Vol. 8, No. 3, June 2004, pp. 204 – 210.
J. F. Schutte, J. A. Reinbolt, B. J. Fregly, R. T. Haftka and A. D. George, “Parallel global optimization with the particle swarm algorithm”, International Journal For Numerical Methods In Engineering, Vol 6, 2004, pp.2296–2315.
Osman, I.H., “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem”, Annals of Operations Research, Vol.41, No.4, 1993, pp.421-451.
Y. Shi, and R. Eberhart, “Parameter Selection in Particle Swarm Optimization, Evolutionary Programming VII”, Proceedings of Evolutionary Programming, 1998, pp. 591-600.
James Kennedy, Russell Eberhart, “Particle Swarm Optimization”, Proceedings of IEEE International Conference on Neural Networks , Vol.4, 1995, pp.1942-1948.
F. Van Den Bergh, A.P. Engelbrecht ,”A study of particle swarm optimization particle trajectories”, Information Sciences , Vol 176, No.8, 2006, pp. 937–971.
Edwin S .H . Hou, Ninvan Ansari, and Hong Ren,“ A genetic algorithm for multiprocessor scheduling”, IEEE Transactions On Parallel And Distributed Systems, Vol. 5, No. 2, 1994, pp.113-120.
Maurice Clerc and James Kennedy, “The Particle Swarm—Explosion, Stability, and Convergence in a Multidimensional Complex Space”, IEEE Transactions On Evolutionary Computation, Vol. 6, No. 1, 2002, pp. .58 – 73.
Ioan Cristian Trelea, “The particle swarm optimization algorithm: convergence analysis and parameter selection”, Information Processing Letters, Vol. 85, 2003, pp. 317–325.
S.Batainah and M.AI – Ibrahim, ”Load management in loosely coupled multiprocessor systems”, Journal of Dynamics and Control, Vol.8, No.1, 1998, pp. 107-116.
Yuhui Shi, “Particle Swarm Optimization”, IEEE Neural Network Society, 2004, pp. 8 -13.
Yskandar Hamam , Khalil S. Hindi, “Assignment of program modules to processors: A simulated annealing approach”, European Journal of Operational Research, Vol. 122, 2000, pp. 509-513.
Annie S. Wu, Han Yu, Shiyuan Jin, Kuo-Chi Lin and Guy Schiavone, “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems, Vol .15, No.9, 2004, pp. 824 -834.
Graham Ritchie, “Static Multi-processor scheduling with Ant Colony Optimization and Local search”, Master of Science thesis, University of Edinburgh, 2003.
S N Sivanandam, P Visalakshi, “Multiprocessor Scheduling using Hybrid Particle Swarm Optimization with dynamically varying inertia”, International Journal of Computer Science and Applications, Vol.4, No.3, 2007, pp.95-106.
Refbacks
- There are currently no refbacks.