Computational models and heuristic methods for Grid scheduling problems

https://doi.org/10.1016/j.future.2009.11.005Get rights and content

Abstract

In this paper we survey computational models for Grid scheduling problems and their resolution using heuristic and meta-heuristic approaches. Scheduling problems are at the heart of any Grid-like computational system. Different types of scheduling based on different criteria, such as static versus dynamic environment, multi-objectivity, adaptivity, etc., are identified. Then, heuristic and meta-heuristic methods for scheduling in Grids are presented. The paper reveals the complexity of the scheduling problem in Computational Grids when compared to scheduling in classical parallel and distributed systems and shows the usefulness of heuristic and meta-heuristic approaches for the design of efficient Grid schedulers. We also discuss on requirements for a modular Grid scheduling and its integration with Grid architecture.

Introduction

Grid computing and Grid technologies primarily emerged for satisfying the increasing demand of the scientific computing community for more computing power. Geographically distributed computers, linked through the Internet in a Grid-like manner, are used to create virtual supercomputers of vast amount of computing capacity able to solve complex problems from e-Science in less time than known before. Thus, within the last years we have witnessed how Grid computing has helped to achieve breakthroughs in meteorology, physics, medicine and other computing-intensive fields. Examples of such large-scale applications are known from optimization [1], [2], [3], Collaborative/e-Science Computing [4], [5] and Data-Intensive Computing [6], to name a few.

Grid computing is still in the development stage, and many challenges are to be addressed. Among these, improving its efficiency is a key issue. The question is: How do we make use of a large number of computers worldwide, ranging from simple laptops, to clusters of computers and supercomputers connected through heterogenous networks in an efficient, secure and reliable manner?

For the majority of Grid systems, scheduling is a very important mechanism. In the simplest of cases, scheduling of jobs can be done in a blind way by simply assigning the incoming tasks to the available compatible resources. Nevertheless, it is a lot more profitable to use more advanced and sophisticated schedulers. Moreover, the schedulers would generally be expected to react to the dynamics of the Grid system, typically by evaluating the present load of the resources, and notifying when new resources join or drop from the system. Additionally, schedulers can be organized in a hierarchical form or can be distributed in order to deal with the large scale of the Grid.

An important issue here is how to formally define the Grid scheduling problem. In this paper we present the most important and useful computational models for this purpose. Then, we focus on the design of efficient Grid schedulers using heuristic and meta-heuristic methods. Heuristic and meta-heuristic methods have proven to be efficient in solving many computationally hard problems. They are showing their usefulness also in the Grid computing domain, especially for scheduling and resource allocation. We analyze why heuristic and meta-heuristic methods are good alternatives to more traditional scheduling techniques and what make them appropriate for Grid scheduling.

The rest of the paper is organized as follows. We present in Section 2 a few important concepts from Grid computing, and introduce a few types of Grids in view of the needs for different types of scheduling and resource allocation. Then, in Section 3 we identify different types of scheduling problems arising in Grid systems. Computational models for Grid scheduling are given in Section 4, while in Section 5 we focus on the current state of using heuristic and meta-heuristic methods for solving scheduling problems in Grid systems. The integration of Grid schedulers into Grid architecture is tackled in Section 6. A few other issues such as security and Grid services scheduling are discussed in Section 7. We end the paper in Section 8 with some conclusions.

Section snippets

The many Grids

The roots of Grid computing can be traced back to the late 1980s and the first concept that laid the basis of today’s Grid systems were developed by researchers from distributed supercomputing for numerical and optimization systems. By the late 1990s, the terms Computational Grids and Grid Computing were popularized by Foster et al. [7], who developed the Globus Toolkit as a general middleware for Grid Systems. Since then, Grid systems have advanced very quickly. In the following subsections we

Scheduling problems in Grid systems

Rather than a problem, scheduling in Grid systems is a family of problems. This is due to the many parameters that intervene scheduling as well as due to the different needs of Grid-enabled applications. In the following, we give some basic concepts of scheduling in Grid systems and identify the most common scheduling types. Needless to say, job scheduling in its different forms is computationally hard; it has been shown that the problem of finding optimum scheduling in heterogeneous systems is

Computational models for Grid scheduling

Given the versatility of scheduling in Grid environments, one needs to consider different computation models for Grid scheduling that would allow one to formalize, implement and evaluate–either in a real Grid or through simulation–different scheduling algorithms. We now present some important computation models for Grid scheduling. It should be noted that such models have much in common with computation models for scheduling in distributed computing environments. We notice that, in all the

Heuristic and meta-heuristic methods for scheduling in Grids

From the exposition in the previous sections, it is clear that the Grid scheduling problem is really challenging. Dealing with the many constraints and optimization criteria in a dynamic environment is very complex and computationally hard. Meta-heuristic approaches are undoubtedly considered the de facto approach. We now point out the main reasons that explain the strength of meta-heuristic approaches for designing efficient Grid schedulers.

  • Meta-heuristics are well understood: Meta-heuristics

Integration of schedulers into Grid architecture

Job scheduling technologies have made it possible to achieve the vision of the high-performance Grid by making tractable many computationally hard problems. Scheduling components, although crucial and useful components of a Grid, are just part of a larger system. The complete vision of a Grid is delivered from the combination of several Grid technology domains that achieve the virtualization: workload virtualization, information virtualization, system virtualization, storage virtualization,

Further issues

Besides the many aspects and facets of the Grid scheduling problem presented in the previous sections, there still remain other issues to be considered. We briefly mention some of them here.

Security is an important aspect to be considered in Grid scheduling. It can be seen as a two-fold objective: tasks could have security requirements to be allocated in secure nodes, while the node itself could have security requirements; that is, the tasks running in the resource will not “watch” or access

Conclusions

In this paper, we have surveyed the most important concepts from Grid computing related to scheduling problems, their resolution using heuristic and meta-heuristic approaches and the integration of Grid schedulers into Grid architectures. After introducing a few important Grid types that have appeared in the Grid computing domain, we identify different types of scheduling based on different criteria, such as static versus dynamic environment, multi-objectivity, adaptivity, etc. Our study

Acknowledgements

Fatos Xhafa’s research work was partially done at Birkbeck, University of London, while on leave from the Technical University of Catalonia (Barcelona, Spain). His research is supported by a grant from the General Secretariat of Universities of the Ministry of Education, Spain.

Fatos Xhafa’s research and teaching experience includes over 15 years in academia in different universities in Europe and the USA. His main research interests include parallel and distributed algorithms, combinatorial optimization, distributed programming, Grid and p2p computing. He is also interested in research issues related to the use of distributed computing systems to the emergent e-learning paradigm. He has widely published in conferences, peer-reviewed articles in international journals

References (81)

  • T. Kosar et al.

    A new paradigm: Data-aware scheduling in grid computing

    Future Generation Computer Systems

    (2009)
  • H. Casanova et al.

    Netsolve: Network enabled solvers

    IEEE Computational Science and Engineering

    (1998)
  • J.P. Goux, S. Kulkarni, J. Linderoth, M. Yoder, An enabling framework for master–worker applications on the...
  • L. Linderoth et al.

    Decomposition algorithms for stochastic programming on a computational grid

    Computational Optimization and Applications

    (2003)
  • H.B. Newman et al.

    Data-intensive e-Science frontier research

    Communications of ACM

    (2003)
  • C. Paniagua, F. Xhafa, S. Caballé, T. Daradoumis, A parallel grid-based implementation for real time processing of...
  • M.D. Beynon, A. Sussman, U. Catalyurek, T. Kure, J. Saltz, Optimization for data intensive grid applications, in: Third...
  • I. Foster et al.

    The Grid—Blueprint for a New Computing Infrastructure

    (1998)
  • M.R. Garey et al.

    Computers and Intractability–A Guide to the Theory of NP-Completeness

    (1979)
  • R. Raman, M. Solomon, M. Livny, A. Roy, The classads language, in: Grid Resource Management: State of the Art and...
  • J.M. Schopf

    Ten actions when grid scheduling

  • J. Cao, S.A. Jarvis, S. Saini, G.R. Nudd, GridFlow: Workflow management for Grid Computing, in: Proc. of the 3rd...
  • J. Yu et al.

    A taxonomy of workflow management systems for grid computing

    Journal of Grid Computing

    (2006)
  • L. Lee, C. Liang, H. Chang, An adaptive task scheduling system for Grid Computing, in: Proceedings of the Sixth IEEE...
  • H. Casanova et al.

    Adaptive scheduling for task farming with grid middleware

    Int. J. High Perform. Comput. Appl.

    (1999)
  • A. Othman et al.

    Adaptive grid resource brokering

    IEEE Int’l Conference on Cluster Computing

    (2003)
  • E. Huedo, R.S. Montero, I.M. Llorente, Experiences on adaptive Grid scheduling of parameter sweep applications, in:...
  • S. Ali, H.J. Siegel, M. Maheswaran, D. Hensgen, Task execution time modeling for heterogeneous computing systems, in:...
  • S. Hotovy, Workload evolution on the Cornell theory center IBM SP2, in: Job Scheduling Strategies for Parallel Proc....
  • N. Fujimoto, K. Hagihara, Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a...
  • Y.C. Lee et al.

    Practical scheduling of bag-of-tasks applications on grids with dynamic resilience

    IEEE Transactions on Computers

    (2007)
  • P. Domingues, A. Andrzejak, L. Silva, Scheduling for fast touraround time on institutional desktop grid. CoreGRID...
  • D. Kondo et al.

    Scheduling task parallel applications for rapid turnaround on enterprise desktop grids

    Journal of Grid Computing

    (2007)
  • J. Gomoluch, M. Schroeder, Market-based resource allocation for Grid Computing: A model and simulation, in: Middleware...
  • P. Fibich et al.

    Model of grid scheduling problem

  • U. Schwiegelshohn, R. Yahyapour, Analysis of First-Come-First-Serve parallel job scheduling, in: Proceedings of the 9th...
  • C. Ernemann, V. Hamscher, R. Yahyapour, Benefits of global grid computing for job scheduling, in: Proceedings of the...
  • F. Xhafa et al.

    Genetic algorithm based schedulers for grid computing systems

    International Journal of Innovative Computing, Information and Control

    (2007)
  • F. Xhafa
  • R.E. Steuer

    Multiple criteria optimization: Theory, computation and application

  • Cited by (0)

    Fatos Xhafa’s research and teaching experience includes over 15 years in academia in different universities in Europe and the USA. His main research interests include parallel and distributed algorithms, combinatorial optimization, distributed programming, Grid and p2p computing. He is also interested in research issues related to the use of distributed computing systems to the emergent e-learning paradigm. He has widely published in conferences, peer-reviewed articles in international journals and chapters in international books. Fatos has co-edited several books and conference proceedings.

    Fatos serves on the editorial board of six peer-reviewed international journals, including Simulation Modelling Practice and Theory (simpat), International Journal of Autonomic Computing (ijac), International Journal of Grid and Utility Computing (ijguc), International Journal of Computer-supported Collaborative Learning (ijcscl) and International Journal of Web Wervices Practices (ijwsp); he has also guest co-edited several international journals. Fatos has served and is currently serving as pc co-chair/general co-chair of several international conferences and workshops.

    Fatos is associate professor (with tenure) at the Technical University of Catalonia and the Open University of Catalonia (Barcelona, Spain) where he teaches several courses, and is currently involved in several research projects sponsored by the European Union, Spain and the USA. Fatos is currently a Visiting Professor at the Department of Computer Science and Information Systems, Birkbeck, University of London (on leave).

    Ajith Abraham’s research and development experience includes over 15 years in the industry and academia spanning different countries in Australia, America, Asia and Europe. His main research interests are in advanced computational intelligence with a focus on hybridizing intelligent techniques involving connectionist network learning, fuzzy inference systems, swarm intelligence, evolutionary computation, distributed artificial intelligence, multi-agent systems and other heuristics. He is also interested in information assurance, network security, e-commerce, semantic web, web intelligence, bioinformatics, financial modeling, decision support systems, data mining applications, etc. He has given plenary lectures and conference tutorials related to hybrid computational intelligence and applications. He has authored/co-authored over 250 peer-reviewed articles, and some of the works have also won best paper awards at international conferences.

    Currently, he is an academic under the IITA professorship program funded by the South Korean Government. He is also a researcher at Rovira i Virgili University, Spain and also holds an adjunct professor appointment in Jinan University, China and Dalian Maritime University, China. He received his Ph.D. degree in Computer Science from Monash University, Australia, and a Master of Science degree from Nanyang Technological University, Singapore.

    He is the editor-in-chief/co-editor in chief of three international scientific journals and also serves on the editorial board of several reputed international journals. He has guest edited 16 special issues for international scientific journals. Since 2001, he has been actively involved in the hybrid intelligent systems (HIS) and the intelligent systems design and applications (ISDA) series of international conferences. He is the general co-chair of the Sixth International Conference on Intelligent Systems Design and Applications (ISDA’06), Jinan, China, and the program co-chair of the Second International Conference on Next Generation Web Services Practices (NWESP’06), Seoul, Korea and the Sixth International Conference on Hybrid Intelligent Systems (HIS’06), Auckland, New Zealand.

    1

    On leave from Technical University of Catalonia, Spain.

    View full text