International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 5, No. 6, 8 May 2013
Cover page and Table of Contents: PDF (size: 333KB)
Enhancing the Discrete Particle Swarm Optimization based Workflow Grid Scheduling using Hierarchical Structure
Full Text (PDF, 333KB), PP.18-26
Views: 0 Downloads: 0
Author(s)
Index Terms
Task Scheduling, Grid Computing, DAG, Particle Swarm Optimization
Abstract
The problem of scheduling dependent tasks (DAG) is an important version of scheduling, to efficiently exploit the computational capabilities of grid systems. The problem of scheduling tasks of a graph onto a set of different machines is an NP Complete problem. As a result, a number of heuristic and meta-heuristic approaches are used over the years due to their ability of providing high quality solutions with reasonable computation time. Discrete Particle Swarm Optimization is one such meta-heuristic used for solving the discrete problem of grid scheduling, but this method converge to sub optimal solutions due to premature convergence. To deal with premature convergence, in this paper we proposed the design and implementation of hierarchical discrete particle swarm optimization (H-DPSO) for dependent task scheduling in grid environment. In H-DPSO particles are arranged in dynamic hierarchy where good particles lying above in hierarchy are having larger influence on the swarm. We consider the bi-objective version of problem to minimize makespan and total cost simultaneously as the optimization criteria. The H-DPSO based scheduler was evaluated under different application task graphs. Simulation analysis manifests that H-DPSO based scheduling is highly viable and effective approach for grid computing.
Cite This Paper
Ritu Garg, Awadhesh Kumar Singh, "Enhancing the Discrete Particle Swarm Optimization based Workflow Grid Scheduling using Hierarchical Structure", International Journal of Computer Network and Information Security(IJCNIS), vol.5, no.6, pp.18-26, 2013. DOI:10.5815/ijcnis.2013.06.03
Reference
[1]Ullman J: NP-complete Scheduling Problems, Journal of Computer and System Sciences. 1975, vol.10, pp. 384-393.
[2]Izakian H, Ladani BT, Zamanifar K, Abraham A: A novel particle swarm optimization approach for grid job scheduling, in Proceedings of the Third International Conference on information Systems, Technology and Management, Springer: Heidelberg, Germany, 2009, pp. 100-110.
[3]Janson S and Middendorf M: A Hierarchical Particle Swarm Optimizer and Its Adaptive Variant, IEEE Transactions on Systems, Man, Cybernatics. Vol.35 (6), 2005, pp.1272-1282.
[4]Braun T D, Siegal H J, Beck N: A comparison of Eleven Static Heuristics for Mapping a Class of independent Tasks onto Heterogeneous Distributed Computing Systems, Journal of Parallel and Distributed Computing, Vol. 61, 2001, pp. 810-837.
[5]Haluk T, Hariri S, Wu MY: Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, Vol. 13, 2002, pp. 260-274.
[6]Bajaj R and Agrawal D P: Improving Scheduling of Tasks in a Heterogeneous Environment, IEEE Transactions on Parallel and Distributed Systems, Vol. 15, 2004, pp. 107-118.
[7]Geras A: A Comparison of Clustering Heuristics for Scheduling Directed Acyclic Graphs on Multiprocessors, In J. of Parallel and Distributed Computing, Vol. 16, No.4, 1992, pp. 276-291.
[8]Subrata R, Zomaya Y A, Landfeldt B: Artificial life techniques for load balancing in computational grids, Journal of Computer and System Sciences, Vol. 73, 2007, pp. 1176-1190.
[9]Yu J and Buyya R: Scheduling Scientific Workflow Applications with Deadline and Budget constraints using Genetic Algorithms, Scientific Programming Journal, Vol. 14(1), 2006, pp. 217-230.
[10]Attiya G, Hamam Y: Task allocation for maximizing reliability of distributed systems: A simulated annealing approach, Journal of Parallel and Distributed Computing, Vol. 66, 2006, pp.1259 – 1266.
[11]Chen WH, Lin CS: A hybrid heuristic to solve a task allocation problem, Computers & Operations Research, Vol. 27, 2000, pp. 287-303.
[12]Ritchie G, Levine J: A fast, effective local search for scheduling independent jobs in heterogeneous computing environments, Technical report, Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, 2003.
[13]Grosan C, Abraham A, and Helvik B: Multi-objective Evolutionary Algorithms for Scheduling Jobs on Computational Grids, IADIS International Conference, Applied Computing 2007, Salamanca, Spain, Nuno Guimares and Pedro Isaias (Eds.), ISBN 978-972-8924-30-0, 2007, pp. 459-463.
[14]Izakian H, Ladani B T, Zamanifar K, Abraham A: A novel particle swarm optimization approach for grid job scheduling, in Proceedings of the Third International Conference on information Systems, Technology and Management, Springer: Heidelberg, Germany,2009, pp. 100-110.
[15]Xhafa F, Abraham A: Metaheuristics for Scheduling in Distributed Computing Environments. ISBN: 978-3-540-69260-7, 2008.
[16]Ratnaweera A, Halgamuge SK and Watson H C: Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients, IEEE Trans. Evol. Comput., Vol. 8, no. 3,2004, pp. 240-255.
[17]Chen CC: Hierarchical Particle Swarm Optimization for Optimization Problems, Tamkang Journal of Science and Engineering, Vol. 12 (3), 2009, pp. 289-298.
[18]Abraham A, Liu H and Zhao M: Particle swarm scheduling for workflow applications in distributed computing environments, Metaheuristics for Scheduling: Industrial and Manufacturing Applications, Studies in Computational Intelligence, Springer Verlag, Germany, 2008, pp. 327-342.
[19]Abraham A, Liu H, Zhang W, Chang TG: Scheduling Jobs on Computational Grids Using Fuzzy Particle Swarm Algorithm, Springer Verlag Berlin Heidelberg, 2006, pp. 500-507.
[20]Chen RM: Application of Discrete Particle Swarm Optimization for Grid Task Scheduling Problem, Advances in grid computing, 2011, DOI: 10.5772/13950.
[21]Chaturvedi K T, Pandit M and Srivastava L: Self-Organizing Hierarchical Particle Swarm Optimization for Nonconvex Economic Dispatch, IEEE Transactions on Power Systems, Vol. 23(3) 2008, pp. 1079-1087.
[22]Jang SH, Wu X, Taylor V, Mehta G, Vahi K and Deelman E: Using performance prediction to allocate grid resources. GriPhyN Technical report 2004-25, 2004.
[23]Jarvis SA, Spooner DP, Keung HNLC, Cao J, Saini S, Nudd GR: Performance prediction and its use in parallel and distributed computing systems, Future Generation Computer System Vol. 22(7), 2006, pp. 745-754.
[24]Shi Y and Eberhart RC: Empirical study of particle swarm optimization, in Proc. IEEE Int. Congr. Evolutionary Computation, Vol. 3, 1999, pp. 101-106.
[25]Kennedy J, Eberhart RC: A discrete binary version of the particle swarm algorithm, IEEE international conference on Systems, Man, and Cybernetics, 1997, pp. 4104 - 4108.
[26]Buyya R, Murshed M: GridSim: A Toolkit for Modeling and Simulation of Grid Resource Management and Scheduling", http://www.buyya.com/gridsim, Vol. 14, 2002, pp. 1175-1220.
[27]Wu M, Gajski D: Hypertool: A programming aid for message passing system, IEEE Transactions on Parallel and Distributed Systems, Vol. 1, 1990, pp. 330-343.