Reference Point Based Multi-Objective Optimization to Workflow Grid Scheduling

Reference Point Based Multi-Objective Optimization to Workflow Grid Scheduling

Ritu Garg (National Institute of Technology, Kurukshetra, India) and Awadhesh Kumar Singh (National Institute of Technology, Kurukshetra, India)
Copyright: © 2012 |Pages: 20
DOI: 10.4018/jaec.2012010105

Abstract

Grid provides global computing infrastructure for users to avail the services supported by the network. The task scheduling decision is a major concern in heterogeneous grid computing environment. The scheduling being an NP-hard problem, meta-heuristic approaches are preferred option. In order to optimize the performance of workflow execution two conflicting objectives, namely makespan (execution time) and total cost, have been considered here. In this paper, reference point based multi-objective evolutionary algorithms, R-NSGA-II and R-e-MOEA, are used to solve the workflow grid scheduling problem. The algorithms provide the preferred set of solutions simultaneously, near the multiple regions of interest that are specified by the user. To improve the diversity of solutions we used the modified form of R-NSGA-II (represented as M-R-NSGA-II). From the simulation analysis it is observed that, compared to other algorithms, R-e-MOEA delivers better convergence, uniform spacing among solutions keeping the computation time limited.
Article Preview

Introduction

Due to development of networking technology, grid computing (Buyya & Venugopal, 2005) has emerged as a promising distributed computing model that facilitates large-scale resource sharing and collaboration. Resources in the grid are highly dynamic and heterogeneous. Scheduling is one of the key challenges of heterogeneous systems. The computational tasks scheduling in grid is a complex optimization problem, which requires careful consideration of different scheduling criteria. Usually, the criteria considered are task execution time, cost of running a task on a machine, reliability, resource utilization etc.

The task scheduling problem is NP-hard (Ullman, 1975); hence, numerous heuristic and meta-heuristic algorithms are proposed in literature to solve the same (Braun et al., 2001; Ye et al., 2006). Many heuristics (Wieczorek et al., 2005; Blythe et al., 2005) have been proposed for workflow grid scheduling in order to optimize single objective, namely minimizing execution time. A considerable number of heuristic algorithms (Wieczorek et al., 2008; Yu et al., 2006; Tsiakkouri et al., 2005) proposed the cost-aware workflow scheduling.

Recently, the research focus has shifted towards handling multiple objectives simultaneously. In multi-dimensional parameter space, no solution can be called best; rather every solution is a trade off among the identified objectives. This makes the requirements specification a real challenge. User may prefer the solution with slightly higher value for some objective, however, with large savings in other. With this motivation, the paper considers two conflicting objectives for task scheduling. We attempt to tradeoff between minimizing the makespan (execution time) and total cost under the specified deadline and budgetary constraint. Genetic Algorithm (GA), based on guided random search technique (Braun et al., 2001), has been used for task scheduling problems. The multi-objective GA with Evolutionary Programming (EP) has been used in (Carretero et al., 2007; Fogel et al., 1996) for task scheduling in grid. The Multi-Objective Evolutionary Algorithm approach (MOEA) combines two major disciplines: Evolutionary computation and theoretical frameworks of multi-criteria decision making.

In workflow grid scheduling problem with multiple objectives, it is not possible to find a single solution which simultaneously optimizes all the objectives; hence, the algorithm, which gives number of alternative solutions lying near the Pareto optimal front, is of great practical value. A decision maker (DM) is perhaps only interested in few Pareto optimal solutions, thus, not all Pareto optimal solutions are generated except those that DM finds interesting. In this study, the preference set of solutions are provided to the decision maker near his/her region(s) of interest simultaneously in single simulation run in order to make better and more reliable decision. Towards this goal we applied two evolutionary algorithms, namely, reference point based non dominated sort genetic algorithm (R-NSGA-II) (Deb et al., 2006) and a reference point based variant of ε-MOEA (Deb et al., 2003), called R-ε-MOEA, henceforth.

Earlier, R-NSGA-II and ε-MOEA has been successfully applied to solve continuous objective functions. In Garg and Singh (2011) we used the R-NSGA-II for the workflow grid scheduling problem considering three objectives simultaneously. Here, in this study, we have proposed a modified version of R-NSGA-II (called M-R-NSGA-II, henceforth) to solve bi-objective discrete problem of workflow grid scheduling. Unlike continuous test problems, in discrete optimization problem, the number of Pareto optimal solutions is relatively small. Moreover, they are not uniformly distributed.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing