An Ant Colony Optimization for Dynamic JobScheduling in Grid Environment

Grid computing is growing rapidly in the distributed heterogeneous systems for utilizing and sharing large-scale resources to solve complex scientific problems. Scheduling is the most recent topic used to achieve high performance in grid environments. It aims to find a suitable allocation of resources for each job. A typical problem which arises during this task is the decision of scheduling. It is about an effective utilization of processor to minimize tardiness time of a job, when it is being scheduled. This paper, therefore, addresses the problem by developing a general framework of grid scheduling using dynamic information and an ant colony optimization algorithm to improve the decision of scheduling. The performance of various dispatching rules such as First Come First Served (FCFS), Earliest Due Date (EDD), Earliest Release Date (ERD), and an Ant Colony Optimization (ACO) are compared. Moreover, the benefit of using an Ant Colony Optimization for performance improvement of the grid Scheduling is also discussed. It is found that the scheduling system using an Ant Colony Optimization algorithm can efficiently and effectively allocate jobs to proper resources.

Authors:

• Siriluck Lorpunmanee
• Mohd Noor Sap
• Abdul Hanan Abdullah
• Chai Chompoo-inwai

Keywords:

• Grid computing
• Distributed heterogeneous system
• Ant colony optimization algorithm
• Grid scheduling
• Dispatchingrules.

References:

[1] I. Foster and C. Kesselman, editors, "The Grid: Blueprint for a New
Computing Infrastructure", Morgan Kaufmann Publishers, 1999.
[2] D.G. Feitelson. "Packing schemes for gang scheduling", In 2nd
Workshop on Job Scheduling Strategies for Parallel Processing, volume
LNCS 1162, pages 89-100, 1996.
[3] D.G. Feitelson, L. Rudolph, U. Schwiegelshohn, K.C. Sevcik, and P.
Wong. "Theory and practice in parallel job scheduling", In 3rd
Workshop on Job Scheduling Strategies for Parallel Processing, volume
LNCS 1291, pages 1-34, 1997.
[4] J. Krallmann, U. Schwiegelshohn, and R. Yahyapour. "On the design
and evaluation of job scheduling algorithms", In 5th Workshop on Job
Scheduling Strategies for Parallel Processing, volume LNCS 1659,
pages 17-42, 1999.
[5] J. M. van den Akker, J. A. Hoogeveen, and J. W. van Kempen. "Parallel
machine scheduling through column generation: Minimax objective
functions", In Y. Azar and T. Erlebach, editors, European Symposium on
Algorithms, volume 2996 of Lecture Notes in Computer Science, pages
648-659. Springer, 2004.
[6] R.D. Nelson, D.F. Towsley, and A.N. Tantawi. "Performance analysis of
parallel processing systems", IEEE Transactions on Software
Engineering, 14(4):532-540, 1988.
[7] V. Hamscher, U. Schwiegelshohn, A. Streit, R.Yahyapour, "Evaluation
of job-scheduling strategies for grid computing", Proceedings of First
IEEE/ACM International Workshop on Grid Computing, Lecture Notes
in Computer Science, vol. 1971, Springer, Berlin, 2000, pp. 191-202.
[8] V. Subramani, R. Kettimuthu, S. Srinivasan, P. Sadayappan,
"Distributed job scheduling on computational grids using multiple
simultaneous requests", Proceedings of the 11th International
Symposium on High Performance Distributed Computing, 2002, pp.
359-366.
[9] H. Shan, L, Oliker and R. Biswas, "Job Superscheduler Architecture and
Performance in Computational Grid Environments", Proceedings of the
ACM/IEEE SC2003 Conference (SC03), 2003.
[10] C. Ernemann , V. Hamscher and R. Yahyapour, "Benefits of Global Grid
Computing for Job Scheduling", Proceedings of the Fifth IEEE/ACM
International Workshop on Grid Computing (GRID-04), 2004.
[11] K. Li, "Job scheduling and processor allocation for grid computing on
Metacomputers ", Journal of Parallel and Distributed Computing,
Elsevier, 2005
[12] T. D. Braun, H. J. Siegel, N. Beck, L. L. Bölöni, M. Maheswaran, A. I.
Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen and R. F.
Freund (2001), "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(6): Pages 810-837.
[13] G. Ritchie and J. Levine, "A fast, effective local search for scheduling
independent jobs in heterogeneous computing environments".
[14] R. Buyya and M. Murshed, "GridSim: A toolkit for the modeling and
simulation of distributed resource management and scheduling for Grid
computing", The Journal of Concurrency and Computation: Practice
and Experience (CCPE), 14:1175-1220, 2002.
[15] D. Fernandez-Baca (1989), "Allocating Modules to Processors in a
Distributed System", IEEE Transactions on Software Engineering. Vol.
15(11): Pages 1427-1436.
[16] D. Klus'aˇcek, L. Matyska, and H. Rudov'a, "Grid scheduling
simulation environment", Submitted to MISTA, 3rd Multidisciplinary
International Scheduling Conference: Theory and Applications, France,
2007.
[17] K. Krauter, R. Buyya and M. Maheswaran, "A taxonomy and survey of
Grid resource management systems for distributed computing", Software
Pract. Exp. 2 (2002) 135-164.
[18] H. Casanova, A. Legrand, D. Zagorodnov and F. Berman, "Heuristics
for scheduling parameter sweep applications in Grid environments", in:
Heterogeneous ComputingWorkshop 2000, IEEE Computer Society
Press, 2000, pp. 349-363.
[19] R. Baraglia, R. Ferrini, and P. Ritrovato, "A static mapping heuristics to
map parallel applications to heterogeneous computing systems",
Research articles. Concurrency and Computation: Practice and
Experience, 17(13):1579-1605, 2005.
[20] P. Fibich, L. Matyska, and H. Rudov'a, "Model of Grid Scheduling
Problem", In Exploring Planning and Scheduling for Web Services, Grid
and Autonomic Computing, Papers from the AAAI-05 workshop.
Technical Report WS-05-03, AAAI Press, 2005.
[21] Z. Xu, X. Hou and J. Sun, "Ant Algorithm-Based Task Scheduling in
Grid Computing", Electrical and Computer Engineering, IEEE CCECE
2003, Canadian Conference, 2003.
[22] E. Lu, Z. Xu and J. Sun, "An Extendable Grid Simulation Environment
Based on GridSim", Second International Workshop, GCC 2003,
volume LNCS 3032, pages 205-208, 2004.
[23] H. Yan, X. Shen, X. Li and M. Wu, "An Improved Ant Algorithm for
Job Scheduling in Grid Computing", In Proceedings of the Fourth
International Conference on Machine Learning and Cybernetics, 18-21
August 2005.
[24] M. Pinedo (1995). "Scheduling -Theory, Algorithms, and Systems",
Prentice Hall.
[25] M. Dorigo and T. Stutzle, "Ant Colony Optimization", The MIT Press.
[26] M. Dorigo and LM. Gambardella, "Ant Colony System: A Cooperative
Learning Approach to the Traveling Salesman Problem", In the IEEE
Transactions on Evolutionary Computation, Vol.1, No.1, pages: 53-66,
1997.