research-article

A novel multi-objective optimization scheme for grid resource allocation

Authors:

Alexander v. d. Kuijl,

Michael T. M. Emmerich,

Hui LiAuthors Info & Claims

MGC '08: Proceedings of the 6th international workshop on Middleware for grid computing

Article No.: 7, Pages 1 - 6

https://doi.org/10.1145/1462704.1462711

Published: 01 December 2008 Publication History

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]

Buyya, R., Murshed, M., Abramson, D., Venugopal, S.: Scheduling parameter sweep applications on global grids: a deadline and budget constrained cost-time optimization algorithm. Software practice and Experience 35 (2005) 491--512

Digital Library

[4]

Casanova, H., Legrand, A., Zagorodnov, D., Berman, F.: Heuristics for scheduling parameter sweep applications in grid environments. In: proceedings of the 9th Heterogeneous Computing Workshop (HCW'2000). (2000) 349--363

Digital Library

[5]

Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley-Interscience Series in Systems and Optimization. John Wiley & Sons, Chichester (2001)

Digital Library

[6]

Dumitrescu, C., Raicu, I., Foster, I.: Di-gruber: A distributed approach to grid resource brokering. In: proceedings of Supercomputing (SC). (2005)

Digital Library

[7]

Ehrgott, M.: Multicriteria Optimization Springer, Berlin, 2005

Digital Library

[8]

Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the Grid: Enabling scalable virtual organizations. Lecture Notes in Computer Science 2150 (2001)

Digital Library

[9]

Ho, N. B., Tay, J. C.: Using evolutionary computation and local search to solve multi-objective flexible job shop problems. In: GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, New York, NY, USA, ACM (2007) 821--828

Digital Library

[10]

Maheswaran, M., Ali, S., Siegel, H. J., Hensgen, D., Freund, R. F.: Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing 59(2) (1999) 107--131

Digital Library

[11]

Nabrzyski, J., Schopf, J. M., (Editors), J. W.: Grid Resource Management: State of the Art and Future Trends. Springer (2003)

Digital Library

[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)

Cited By

Dutta Pramanik PBiswas TChoudhury P(2022)Multicriteria-based Resource-Aware Scheduling in Mobile Crowd Computing: A Heuristic ApproachJournal of Grid Computing10.1007/s10723-022-09633-y21:1Online publication date: 20-Dec-2022
https://doi.org/10.1007/s10723-022-09633-y
Lytvyn VVysotska VBublyk MGozhyj ASchuchmann V(2021)Solving Scheduling Issues Methods Analysis in Computational Grid2021 IEEE 16th International Conference on Computer Sciences and Information Technologies (CSIT)10.1109/CSIT52700.2021.9648590(267-273)Online publication date: 22-Sep-2021
https://doi.org/10.1109/CSIT52700.2021.9648590
Quezada-Pina ATchernykh AGonzález-García JHirales-Carbajal ARamírez-Alcaraz JSchwiegelshohn UYahyapour RMiranda-López V(2018)Adaptive parallel job scheduling with resource admissible allocation on two-level hierarchical gridsFuture Generation Computer Systems10.1016/j.future.2012.02.00428:7(965-976)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2012.02.004

Index Terms

A novel multi-objective optimization scheme for grid resource allocation
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

A robust multi-objective resource allocation scheme incorporating uncertainty and service differentiation
Advanced Scheduling Strategies and Grid Programming Environments

Grid computing emerges as an infrastructure for large-scale data processing, resource sharing, and scientific computing. In this paper we propose a Grid scheduling algorithm using multi-attribute utility theory and multi-objective optimization (MOO). ...
Meta-schedulers for grid computing based on multi-objective swarm algorithms

Job scheduling is a challenging task on grid environments because they must fulfill user requirements. Scientists often have deadlines and budgets for their experiments (set of jobs). But these requirements are in conflict with each other - cheaper ...
Multi-objective optimization using teaching-learning-based optimization algorithm

Two major goals in multi-objective optimization are to obtain a set of nondominated solutions as closely as possible to the true Pareto front (PF) and maintain a well-distributed solution set along the Pareto front. In this paper, we propose a teaching-...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

MGC '08: Proceedings of the 6th international workshop on Middleware for grid computing

December 2008

72 pages

ISBN:9781605583655

DOI:10.1145/1462704

Conference Chairs:
Bruno Schulze
LNCC, Brazil
,
Geoffrey C Fox
Indiana University

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Middleware '08

Middleware '08: 9th International Middleware Conference

December 1 - 5, 2008

Leuven, Belgium

Acceptance Rates

Overall Acceptance Rate 14 of 36 submissions, 39%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
245
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dutta Pramanik PBiswas TChoudhury P(2022)Multicriteria-based Resource-Aware Scheduling in Mobile Crowd Computing: A Heuristic ApproachJournal of Grid Computing10.1007/s10723-022-09633-y21:1Online publication date: 20-Dec-2022
https://doi.org/10.1007/s10723-022-09633-y
Lytvyn VVysotska VBublyk MGozhyj ASchuchmann V(2021)Solving Scheduling Issues Methods Analysis in Computational Grid2021 IEEE 16th International Conference on Computer Sciences and Information Technologies (CSIT)10.1109/CSIT52700.2021.9648590(267-273)Online publication date: 22-Sep-2021
https://doi.org/10.1109/CSIT52700.2021.9648590
Quezada-Pina ATchernykh AGonzález-García JHirales-Carbajal ARamírez-Alcaraz JSchwiegelshohn UYahyapour RMiranda-López V(2018)Adaptive parallel job scheduling with resource admissible allocation on two-level hierarchical gridsFuture Generation Computer Systems10.1016/j.future.2012.02.00428:7(965-976)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2012.02.004

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten