Using Genetic Algorithm for Scheduling Tasks of Computational Grids in the Gridsim Simulator

Introduction

Since the computing outset, one the most interesting issue in this research area has been the increase of computer power processing (Distefano, et al., 2010). As time passes, new software technologies require hardware increasingly powerful (Bahi, Contassot-Vivier & Couturier, 2007). This technology trend has demanded from processors distributors a fast technological development. However, many times, the technology used in a processor cannot alone satisfy the cases which the resources processing demand is huge, emerging as well, the parallel machines with a larger number of processors (Davis & Petrini, 2004).

For some applications, a large number of processors makes an inappropriate solution, due to the project economic viability in the construction or acquisition of suitable parallel machines (Baduel, L., et al., 2006). The grid computing has become a viable solution for those cases which present a great processing demand (Baduel, et al., 2006; Foster, 2002; Foster, Kesselman & Tuecke, 2001).

According to (Foster, 2002; Foster, Kesselman & Tuecke, 2001; Hey & Trefethen, 2003; Taurion, 2010) the grid computing is a distributed computing model that uses geographically and administratively the available resources. Individual users may access the computers and the data in a transparent way, without considering geographical position, operating system, accounts administration and other details (Buckley, 2010).

In grids computing, the details are abstracted and the resources are virtualized (Gentzsch, Grandinetti & Joubert, 2010) i.e., the whole computational grid is showed to user as a unique resource. The grid used can be done in many areas that require large amount of processing such as: image processing, optimizing calculation, pharmaceutical industry, natural disaster simulations, etc. A huge problem faced in grid computing is the tasks scheduling, although it is known as an allocation problem (Foster, 2002). it differs from allocation problems in the conventional distributed systems. This problem is much more complex, given the dynamic nature (in which come in and out of the grid, use restrictions, etc.) and the high degree of resources heterogeneity (architectures, operating systems, different location) and tasks that must be monitored. According to (Garey & Johnson, 1990) the tasks scheduling is a NP-complete problem, and according to (Luke, 2009). using heuristics is in fact, the most used approach in practice in order to deal with the difficulty in problems with these features. In (Linden, 2012). the genetic algorithms usually present a better performance than the specific heuristics. In optimization problems, if one wishes to achieve a goal or a value, even if it is in an interval, this is called objective or objective function (Abraham, Buyya & Nath, 2000). The objective can be maximized or minimized, seeking the maximum values or minimum for the problems' functions, complying with restrictions presented for the model.

The scheduling problem presents many goals to be achieved in a general way, for instance, reduce the total time for the tasks execution, reduce the total time of idle processors, increase the processing efficiency. In this paper, we have considered two goals: time execution of each task and the total time of the system execution. In Figure 1 is shown an example of a computational grid, which a user sends a task block for the scheduler, and it divides the tasks among the available computers for processing, receiving the tasks processed and sending back to the user.

Figure 1.

Example of computational grid operation