A COST EFFICIENT TWO-LEVEL MARKET MODEL FOR TASK SCHEDULING PROBLEM IN GRID ENVIRONMENT

10.22099/ijste.2014.2099

Abstract

This paper investigates the scheduling problem of independent tasks in market-based
grids . The heterogeneity and autonomy of resources in grids highlight the need for more flexible
models and approaches to be exploited in these environments. To address this issue, a two-level
market model is presented in this paper to schedule tasks to the grid resources. In the proposed
model , users submit their own tasks to a centralized resource manager named meta-scheduler .
Meta-scheduler knows general information about each of the administrative domains , called sites ,
existing in the low-level part of the model. Using the information gathered from all of the sites ,
meta-scheduler selects more suitable sites to execute the tasks with the aim of minimizing the
overall cost of tasks execution . In this model, meta-scheduler not only targets the minimization of
overall cost of the tasks execution, but also achieves this objective without any presumption about
the policies and algorithms implemented in the lower layers of the system which addresses the
dynamicity of environment. In addition to the two-level market model , a new task scheduling
algorithm called GA-VNS which is an enhanced version of genetic algorithm is presented to be
applied in market-based grids. GA-VNS can be used by local schedulers in each site with the
policy of cost minimization considering the makespan of the system as a second criterion. The
results obtained from performance evaluation of GA-VNS and other well-known algorithms in this
context show that GA-VNS outperforms other algorithms in terms of the overall cost of tasks
execution .

Keywords