Optimization Techniques for Solving Complex Problems

CHAPTER 24

Experimental Study of GA-Based Schedulers in Dynamic Distributed Computing Environments

F. XHAFA and J. CARRETERO

Universitat Politècnica de Catalunya, Spain

24.1 INTRODUCTION

In this chapter we address the issue of experimental evaluation of metaheuristics for combinatorial optimization problems arising in dynamic environments. More precisely, we propose an approach to experimental evaluation of genetic algorithm–based schedulers for job scheduling in computational grids using a grid simulator. The experimental evaluation of metaheuristics is a very complex and time-consuming process. Moreover, ensuring significant statistical results requires, on the one hand, testing on a large set of instances to capture the most representative set of instances, and on the other, finding appropriate values of the search parameters of the metaheuristic that would be expected to work well in any instance of the problem.

Taking into account the characteristics of the problem domain under resolution is among the most important factors in experimental studies of the metaheuristics. One such characteristics is the static versus dynamic setting. In the static setting, the experimental evaluation and fine tuning of parameters is done through benchmarks of (static) instances. An important objective in this case is to run the metaheuristic a sufficient number of times on the same instance and ...