An Ant Colony Optimization for Dynamic JobScheduling in Grid Environment

Authors: Siriluck Lorpunmanee, Mohd Noor Sap, Abdul Hanan Abdullah, Chai Chompoo-inwai

Abstract:

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.

Keywords: Grid computing, Distributed heterogeneous system, Ant colony optimization algorithm, Grid scheduling, Dispatchingrules.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330229

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.