Abstract

Grid computing provides the means of using and sharing heterogeneous resources that are geographically distributed to solve complex scientific or technical problems. Task scheduling is critical to achieving high performance on grid computing environment. The objective of the scheduling process is to map each task with specific requirements to a capable machine in order to minimize the makespan. Task scheduling is shown to be NP-complete problem, which can be solved using heuristic algorithms. Several heuristic algorithms have been proposed in the literature, and they are either not efficient or complex. In this paper, we are proposing a Multi Objectives heuristic Algorithm to minimize the makespan and flow time and to maximize the resource utilization with a low computational complexity.

References

• I. Foster, and C. Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Second Edition, Elsevier and Morgan Kaufmann Press, 2004.
• Zhou Lei and Zhifeng, Allen, Gabrielle Yun, "Grid Resource Allocation," in Grid Computing: Infraestructure, Service, and Applications, Lizhe Wang, Wei Jie, and Jinjun Chen, Eds. Boca Raton: CRC Press, 2009, ch. 7, pp. 1172-188.
• Hojjat Baghban, Amir Masoud Rahmani, " A Heuristic on Job Scheduling in Grid Computing Environment", In Proceedings of the seventh IEEE International Conference on Grid and Cooperative Computing, pp. 141-146, 2008. 3605-7, pp. 8-12, 2009.
• Li Wenzheng, Zhang Wenyue, " An Improved Scheduling Algorithm for Grid Tasks", International Symposium on Intelligent Ubiquitous Computing and Education, pp. 9-12, 2009.
• Hesam Izakian, Ajith Abraham, and Václav Snasel, "Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments," vol. 1, pp. 8-12, 2009.
• Fatos Xhafa and Ajith Abraham, Meta-heuristics for Scheduling in Distributed Computing Environments. : Springer-Verlag Berlin Heidelberg, 2008, pp. 1-38, 247-272.
• T. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheshwaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen, and R. Freund, "A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems", In 8th IEEE Heterogeneous Computing Workshop(HCW'99), pp. 15-29, 1999.
• Tracy D. Braun, Howard Jay Siegel, and Noah Beck, "A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems", Journal of Parallel and Distributed Computing 61, pp. 810-837, 2001.
• Miguel L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fifth Edition. : Springer, 2008.
• Izakian Hesam, Abraham Ajith and Snasel Vaclav, Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments, The 2009 IEEE International Workshop on HPC and Grid Applications (IWHGA2009), China, IEEE Press, USA, ISBN 978-0-7695- 3605-7, pp. 8-12, 2009.
• J. M. Schopf, "A General Architecture for Scheduling on the Grid", special issue of JPDC on Grid Computing, 2002.
• R. F. Freund, and M. Gherrity, "Scheduling Resources in Multi-user Heterogeneous Computing Environment with Smart Net", In Proceedings of the 7th IEEE HCW, 1998.
• R. Armstrong, D. Hensgen, and T. Kidd, "The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions", In 7th IEEE Heterogeneous Computing Workshop(HCW'98), pp. 79-87, 1998.
• R. F. Freund and H. J. Siegel,"Heterogeneous Processing", IEEE Computer, 26(6), pp. 13-17, 1993.
• M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, Dynamic mapping of a class of independent tasks onto heterogeneous computing systems, J. Parallel Distributed Computing 59, 2 (Nov. 1999), 107_121
• J. Brevik, D. Nurmi, and R. Wolski, "Automatic Methods for Predicting Machine Availability in Desktop Grid and Peer-to-Peer Systems", In Proceedings of CCGRID'04, pp. 190-199, 2004.