The Scheduling Algorithm of Grid Task Based on PSO and Cloud Model

Abstract:

Grid task scheduling (GTS) is a NP-hard problem. This paper proposes an optimized GTS algorithm which combines with the advantages of cloud model based on the particle swarm optimization algorithm. This algorithm iterates tasks utilizing the advantages of particle swarm optimization algorithm and then gets a set of candidate solutions quickly. In addition, this algorithm modifies the value of entropy and excess entropy using the characteristics of cloud model and implements the transformation between qualitative variables and quantity of uncertain events. And this algorithm makes particles fly to the global optimal solutions by exact searching in local areas. Theoretical analysis and simulation results show that this algorithm makes load balance of resource efficiently. It also avoids the problems of genetic algorithm and basic particle swarm optimization algorithm, which would easily fall into local optimal solutions and premature convergence caused by too much selected pressure. This algorithm has the advantages of high precision and faster convergence and can be applied in task scheduling on computing grid.

• Periodical: Key Engineering Materials (Volumes 439-440)
• Pages: 1487-1492
• DOI: https://doi.org/10.4028/www.scientific.net/KEM.439-440.1487
• Online since: June 2010
• Authors: Shao Bo Zhong, Zhong Shi He
• Keywords: Cloud Model, Grid Computing, Particle Swarm Optimization Algorithm (PSO), Task Scheduling

References

[1] Rajkumar Buyya, David Abramson, Jonathan Giddy. Grid Resource Management, Scheduling, and Computing Economy [C]. The 1st International Workshop on Grid and Cooperative Computing, Tokyo, Japan: IEEE Computer Society, 2000, pp: 1734-1739.

[2] Li Chunlin , Lu Zhengding , Li Layuan. An Agent-based Approach for Grid Resource Management [J], Journal of Wuhan University of Technology, 2003, 29(15): 110-115.

[3] Yao jun Han, Resource Scheduling Algorithm for Grid Computing and Its Modeling and Analysis Using Petri Net[C]. The 2nd International Workshop on Grid and Cooperative Computing, Shanghai, IEEE Computer Society, 2003: 814-820.

DOI: 10.1007/978-3-540-24680-0_10

[4] Zhi hong Xu, Xiangdan Hou. Ant Algorithm-based Task Scheduling in Grid Computing[C]. Proc of Conf on Electrical and Computer Engineering, Quebec Canadian：IEEE Computer Society, 2003: 1107-1110.

DOI: 10.1109/ccece.2003.1226090

[5] Vincenzo Di Martino. Schduling in a grid computing enviroment using genetic algorithm[C]. The 16th Int'1 Parallel and Distributed Processing Symp, Pittsburgh, USA：Kluwer Academic press, 2002: 678-686.

[6] JI Yi-mu; WANG Ru-chuan. Study on PSO algorithm in solving grid task scheduling [J], Journal on Communications, 2007, 28(10): 0060-0066.

[7] YI Kan; WANG Ru-chuan. Nash Equilibrium Based Task Scheduling Algorithm of Multi-schedulers in Grid Computing [J], Acta Electronica Sinica, 2009, 37( 2): 0329-0333.

[8] Li Deyi，Meng Haljan, Shi Xuemei. Membership Clouds and Membership cloud Generators (J), Journal of Computer Research and Development, 1995, 32(6): 15-20.

[9] ZHANG Guang-Wei, HE Rui, LIU Yu, LI De-Yi, CHEN Gui-Sheng. An Evolutionary Algorithm Based on Cloud Model [J]. Chinese Journal of Computers, 2008, 31(7): 1082-1091.

DOI: 10.3724/sp.j.1016.2008.01082

[10] XIE Xiao-feng, ZHANG Wen-jun, YANG Zhi-lian. Overview of particle swarm optimization [J]. Control and Decision, 2003, 18(2): 129-134.

DOI: 10.1109/icosp.2002.1180009

[11] Liang J J, Qin A K. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computing, 2006, 10(3): 281-295.

DOI: 10.1109/tevc.2005.857610