Multi-objective Grid Scheduling

Grid computing is a distributed paradigm that coordinates heterogeneous resources using decentralized control. Grid computing is commonly used by scientists for executing experiments. Scheduling jobs within Grid environments is a challenging task. Scientists often need to ensure not only a successful execution for their experiments but also they have to satisfy constraints such as deadlines or budgets. Both of these constraints, execution time and cost, are not trivial to satisfy, as they are conflict with each other, eg cheaper resources are usually slower than expensive ones. Hence, a multi-objective scheduling optimization is a more challenging task in Grid infrastructures. This chapter presents a new multi-objective approach, MOGSA (Multi-Objective Gravitational Search Algorithm), based on the gravitational search behaviour in order to optimize both objectives, execution time and cost, with the same importance and also at the same time. Two studies are carried out in order to evaluate the quality of this new approach for grid scheduling. Firstly, MOGSA is compared with the multiobjective standard and well-known NSGA-II (Non-Dominated Sorting Genetic Algorithm II) to prove the multi-objective optimization suitability of the proposed algorithm. Secondly two real grid schedulers (WMS and DBC) are also compared with MOGSA. TheWMS (WorkloadManagement System) is considered because of it is part of the most used European grid middleware - gLite - and also the DBC (Deadline Budget Constraint) algorithm from Nimrod-G participates in this evaluation due to its good performance keeping the deadline and budget per job. Results point out the superiority of MOGSA in all the studies carried out. MOGSA offers more quality solutions than NSGA-II and also better performance than current real schedulers.