Abstract

Grid facilitates global computing infrastructure for user to consume the services over the network. To optimize the workflow grid execution, a robust multi-objective scheduling algorithm is needed. In this paper, we considered three conflicting objectives like execution time (makespan), total cost and reliability. We propose a multi-objective scheduling algorithm, using R-NSGA-II approach based on evolutionary computing paradigm. Simulation results shows that the proposed algorithm generates multiple scheduling solutions near the Pareto optimal front with small computation overhead.

References

• Foster, I., Kesselman, C. 1999. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, ISBN 1-55860-475-8, San Francisco.
• Braun, T., Siegal, H., Beck, N. 2001. A comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. In: Journal of Parallel and Distributed Computing, vol. 61, 810-837.
• X, He., XH, Sun., GV, Laszewski. 2003. QoS Guided min–min Heuristic for Grid Task Scheduling. In: Journal of Computer Science and Technology, vol. 18(4), 442-451.
• Wang, L., Siegel, H., Roychowdhury, V., Maciejewski, A. 1997. Task Matching and Scheduling in Heterogeneous Computing Environments using a Genetic-Algorithm-Based Approach. In: Journal of Parallel Distributed Computing, vol. 47, 9–22.
• Wieczorek, M., Prodan, R., Fahringer, T. 2005. Scheduling of Scientific Workflows in the ASKALON Grid Environment. SIGMOD Rec., vol. 34, 56-62, ACM
• Wieczorek, M., Podlipning, S., Prodan, R., Fahringer, T. 2008. Bi-criteria Scheduling of Scientific Workflows for the Grid. 978-0-7675-3156-4/08, IEEE.
• Yu, J., Buyya, R. 2006. Scheduling Scientific Workflow Applications with Deadline and Budget Constraints using Genetic Algorithms. Scientific Programming, vol. 14, 217-230.
• Tsiakkouri, E., Sakellariou, R., Zhao, H., Dikaiakos, M. 2005. Scheduling Workflows with Budget Constraints. In: CoreGRID Integration Workshop, 347-357.
• Haluk, T., Hariri, S., Wu, M. 2002. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. In: IEEE Transactions on Parallel and Distributed Systems, vol. 13, 260-274.
• Prodan, R., Fahringer, T. 2005. Dynamic scheduling of Scientific Workflow Applications on the Grid: A case study. In: SAC 05: Proceedings of the 2005 ACM Symposium on Applied Computing, 687–694.
• Yu, J., Kirley, M., Buyya, R. 2007. Multi-objective Planning for Workflow Execution on Grids. In: Proceedings of the 8th IEEE/ACM International conference on Grid Computing, ISBN:978-1-4244-1559-5, doi.10.1109/GRID.2007. 4354110.
• Talukder, A., Kirley, M., Buyya, R. 2009. Multiobjective Differential Evolution for Scheduling Workflow Applications on Global Grids. doi: 10.1002/cpe.1417, John Wiley & Sons, Ltd.
• Deb, K. 2001 Multi-Objective Optimization using Evolutionary Algorithms. Wiley and Sons, England.
• Deb, K., Pratap, A., Aggarwal, S., Meyarivan, T. 2000. A Fast Elitist Multi-Objective Genetic Algorithm: NSGA-II. In: Parallel Problems Solving from Nature VI, 849-858.
• Zitzler, E., Laumanns, M., Thiele, L. 2001. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In: K.C. Giannakoglou, D.T. Tshalis, J. Periaux, K. D. Papailion, T. Fogarty (eds), Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, 95-100, Athens, Greece.
• Knowles, J., Corne, D. 1999. The Pareto Archive Evolution Strategy: A New Baseline Algorithm for Multi-Objective Optimization, In: The congress on Evolutionary Computation, pp. 98-105.
• K. Deb, J. Sundar, U. R. Rao, S. Choudhuri. 2006. “Reference Point Based Multi-Objective Optimization Using Evolutionary algorithms”, International Journal of Computational Intelligence Research, ISSN 0973-1873 vol.2, No.3, 273–286.
• Camelo, M., Donoso, Y., Castro, H. 2010. A Multi-Objective Performance Evaluation in Grid Task Scheduling using Evolutionary Algorithms. In: Applied Mathematics and Informatics, ISBN: 978-960-474-260-8.
• Navimipour, N., Es-hagi, S. LGR. 2009. The New Genetic Based Scheduler for Grid Computing Systems. In: International Journal of Computer and Electrical Engineering, Vol. 1, No. 5, 610-614.
• Grosan, C., Abraham, A., Helvik, B. 2007. Multiobjective Evolutionary Algorithms for Scheduling Jobs on Computational Grids. In: International Conference on Applied Computing, Spain. ISBN 978-972-8924-30-0, 459-463.
• Dogan, A., Ozguner, F. 2005. Biobjective Scheduling Algorithms for Execution Time-Reliability trade-off in Heterogeneous Computing Systems. Comput. J., vol. 48, no. 3, 300-314.
• Buyya, R. GridSim: A Toolkit for Modeling and Simulation of Grid Resource Management and Scheduling, http://www.buyya.com/gridsim.
• Deb, K., Jain, S. 2002. Running Performance Metrics for Evolutionary Multi-objective Optimization. In: Simulated Evolution and Learning (SEAL-02), 13-20
• Do, T., Nguyen, T., Nguyen, D., Nguyen H., Le, T. Failure-aware Scheduling in Grid Computing Environments.
• Chitra, P., Revathi, S., Venkatesh, P., Rajaram, R. 2010. Evolutionary Algorithmic Approaches for Solving Three Objective Task Scheduling Problem on Heterogeneous Systems. In: 2nd International IEEE Conference on Advance Computing, ISBN 978-1-4244-4791-6/10, IEEE.