A novel multi-objective optimization scheme for grid resource allocation

ABSTRACT

Grid computing emerges as an infrastructure for large-scale data processing, resource sharing, and scientific computing. Job scheduling at the Grid level is challenging in that Grid schedulers do not have control over the computing resources across multiple domains. This makes many traditional algorithms developed on parallel systems not suitable in the Grid case. In this paper we propose a Grid scheduling algorithm using multi-attribute utility theory and multiobjective optimization. It attempts to make optimal decisions based on the available set of objectives. By comparing to a deadline-and-budget algorithm with three objectives, we show that the proposed Multi-Objective Optimization (MOO) scheduling algorithm is capable of obtaining a broader set of non-dominated solutions, and can obtain solutions of higher quality, that is proximity to the Pareto front of optimal solutions.

REFERENCES

• 1: Beume, N., Naujoks, B., and Emmerich, M.: Sms-emoa: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 127, 3 (September 2007), 1653--1669. available at http://ideas.repec.org/a/eee/ejores/v181y2007i3p1653-1669.html.
• 2: Buyya, R., and Murshed, M.: Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Concurrency and Computation: Practice and Experience (CCPE) 14 (2002).
• 3: Rajkumar Buyya , Manzur Murshed , David Abramson , Srikumar Venugopal, Scheduling parameter sweep applications on global Grids: a deadline and budget constrained cost-time optimization algorithm, Software—Practice & Experience, v.35 n.5, p.491-512, 25 April 2005 [doi>10.1002/spe.646]
• 4: Henri Casanova , Dmitrii Zagorodnov , Francine Berman , Arnaud Legrand, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proceedings of the 9th Heterogeneous Computing Workshop, p.349, May 01-01, 2000
• 5: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 6: Catalin Dumitrescu , Ioan Raicu , Ian Foster, DI-GRUBER: A Distributed Approach to Grid Resource Brokering, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.38, November 12-18, 2005 [doi>10.1109/SC.2005.23]
• 7: Matthias Ehrgott, Multicriteria Optimization, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 8: Ian T. Foster, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.1-4, August 28-31, 2001
• 9: Nhu Binh Ho , Joc Cing Tay, Using evolutionary computation and local search to solve multi-objective flexible job shop problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277121]
• 10: Muthucumaru Maheswaran , Shoukat Ali , Howard Jay Siegel , Debra Hensgen , Richard F. Freund, Dynamic mapping of a class of independent tasks onto heterogeneous computing systems, Journal of Parallel and Distributed Computing, v.59 n.2, p.107-131, Nov. 1999 [doi>10.1006/jpdc.1999.1581]
• 11: Jarek Nabrzyski , Jennifer M. Schopf , Jan Weglarz, Grid resource management: state of the art and future trends, Kluwer Academic Publishers, Norwell, MA, 2004
• 12: Naujoks, B., Beume, N., and Emmerich, M.: Multi-objective optimisation using s-metric selection: application to three-dimensional solution spaces. In Evolutionary Computation, 2005. The 2005 IEEE Congress on Publication Date: 2--5 Sept. 2005 (Piscataway, NY, 2005), vol. 2, IEEE Press, pp. 1282--1289.
• 13: Song, S., Hwang, K., Kwok, Y. K.: Trusted grid computing with security binding and trust integration. Journal of Grid Computing 3 (2005) 53--73
• 14: Steuer, R. E.: Multiple Criteria Optimization: Theory, Computation and Application. John Wiley, New York, 546 pp (1986)
• 15: Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Gloriastrasse 35, CH-8092 Zurich, Switzerland (2001)

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Experimentation, Performance

Keywords:
grid-computing, multi-attribute utility functions, multi-objective optimization, scheduling