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

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.