IJSER Home >> Journal >> IJSER
International Journal of Scientific and Engineering Research
ISSN Online 2229-5518
ISSN Print: 2229-5518 6    
Website: http://www.ijser.org
scirp IJSER >> Volume 2, Issue 6, June 2011 Edition
Balanced Ant Colony Algorithm For Scheduling DAG To Grid Heterogeneous System
Full Text(PDF, 3000)  PP.  
Mrs. Smitha Jha,Dr. D. K. Mallik,Dr. R.K. Suri
Grid System, Directed Acyclic graph(DAG),Independent, Dependent task scheduling, Ant Colony Optimization, Grouping, Ranking
Ant Colony Optimization can be used for scheduling tasks on resources in Grid. In earlier work this technique has been applied for independent task scheduling. This paper apply the above technique for dependent task scheduling. Here a hybrid algorithm by Sakellariou can be applied,where tasks in DAG(Directed acyclic graph) are upward ranked and sorted decreasingly. Then the sorted tasks are grouped along the sorted sequences and in every group,tasks are independent. Then independent task groups can be scheduled to resources using algorithm specified by author Chang.
[1] An ant algorithm for balanced job scheduling in grids Ruay-Shiung Chang_, Jih-Sheng Chang, Po- Sheng Lin Department of Computer Science and Information Engineering, National Dong Hwa University, Shoufeng Hualien, 974 Taiwan, ROC

[2].A Hybrid heuristic for DAG Scheduling on Heteorogeneous Systems. Rizos Sakellario and Henan Zhao ,Department of Computer Science,University of Manchester,Oxford Road,Manchester M13 9PL,U.K.

[3]. Fangpeng Dong and Selim G. Akl “Scheduling Algorithms for Grid Computing: State of the Art and Open Problems” Technical Report No. 2006- 504

[4]. M. Dorigo, C. Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2–3) (2005) 243–278.

[5]. M. Dorigo, Ant colony optimization, http://www.aco-metaheuristic.org.

[6]. M. Dorigo, L.M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1 (1) (1997) 53–66.

[7]. E. Salari, K. Eshghi, An ACO algorithm for graph coloring problem, in: Congress on Computational Intelligence Methods and Applications, 15–17 Dec. 2005, p. 5.

[8]. Xiaoxia Zhang, Lixin Tang, CT-ACO— hybridizing ant colony optimization with cycle transfer search for the vehicle routing problem, in: Congress on Computational Intelligence Methods and Applications, 15–17 Dec. 2005, p. 6.

[9]. T. Stutzle, MAX-MIN Ant System for Quadratic Assignment Problems Technical Report AIDA-97-04, Intellectics Group, Department of Compute Science, Darmstadt University of Technology, Germany, July 1997.

[10]. B. Bullnheimer, R.F. Hartl, C. Strauss, A new rank-based version of the ant system: A computational study, Central European Journal for Operations Research and Economics 7 (1) (1999) 25–38. 190

[11]. E.D. Taillard, L.M. Gambardella, Adaptive memories for the quadratic assignment problem, Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.

[12]. M. Dorigo, V. Maniezzo, A. Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B 26 (1) (1996) 29–41.

[13]. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating System Concepts, 7th edition, John Wiley & Sons, 2005.

[14]. D. Saha, D. Menasce, S. Porto, Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures, Journal of Parallel and Distributed Computing 28 (1) (1995) 1–18.

[15]. D. Paranhos, W. Cirne, F. Brasileiro, Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids, in: International Conference on Parallel and Distributed Computing (Euro- Par), in: Lecture Notes in Computer Science, vol. 2790, 2003, pp. 169–180.

[16]. M. Maheswaran, S. Ali, H.J. Siegel, D. Hensgen, R. Freund, Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing system, Journal of Parallel and Distributed Computing 59 (1999) 107–131

Untitled Page