Cuckoo Genetic Optimization Algorithm for Efficient Job Scheduling with Load Balance in Grid Computing

Published Online August 2016 in MECS DOI: 10.5815/ijcnis.2016.08.07

Fame of internet with accessibility of high bandwidth structure of networks requires dispersed multi-user machines. Current searches in computer science launched a recent concern known as "Grid Computing" [1]. Grid computing is collection of machines or systems or computers or system resources from several distributed locations to achieve a common objective. Grid develops a system having non-interactive workloads which has a large number of folders or files or both. It is a method in resolving comprehensive struggles in commerce, technical science (engineering), medical science and computer science [2]. This computing engages sharing and management of sources, management and description of information, task scheduling, and load balancing so on. Goal of such computing is to utilize assigned resources obtainable for compound calculating by webs that all sites were dispersed geographically. Major plan of this system is resources sharing among coats of software and be utilized for simplicity and privacy. It is accountable for resources search and virtualization having direct running request. Grids in computational forms have the simple logic for computing and having dispersed computations. Logic is consideration with an easy virtual machines having huge and powerful system that has capability for controlling a broad set of machines. Such set having heterogeneous machines linked with each other with a variety of resources in shared format.

Allotment of shared resources over time to challenge performance in grid system is scheduling. It has been the subject of an important quantity of literature in the actions search area. Importance has been on examining computers and their scheduling troubles where tasks mention the performance and systems mention the resources.

Task scheduling problem in DAG (Directed acyclic graph) in parallel computing is similar to a NP Complete problem. Many heuristic or meta-heuristic techniques provides better results with appropriate computation time by using Particle Swarm Optimization (PSO) in grid scheduling [20]. Heuristic scheduling algorithms [3] [4] [5] are frequently used in heterogeneous computing situations. A resource be processed or used either in exclusive form or shared form. The mechanisms used for determining whether or not a set of jobs is schedulable or not in such an environment and to find the best optimized solution for setting the best scheduling system is heuristic schedule. Such type of problem is called NP complete and so methodically study of set of heuristics can be applied by such algorithms. Due to the complexity of the problem, simple heuristics do not perform satisfactorily. However, an algorithm that uses combinations of these simple heuristics works very well compared to an optimal algorithm that takes exponential time complexity. In dynamic grid systems, implementation workload and time cannot be detected during processing. So scheduling of grid requires prognostic models.

Cuckoo is a search mechanism and is an optimization technique developed by Xin-she Yang and Suash Deb in 2009. Cuckoo was encouraged by the obliged brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds (of other species). Here

Cuckoo Genetic optimization Algorithm (CGOA) is a meta-heuristic technique to solve problem related with task scheduling in grid system. CGOA is stimulated by cuckoo search and genetic mechanism. This has ability of non-local pointing with lesser constraints as comparison to GA. Having a sequential imitated set up (experiment), results demonstrate that CGOA is efficient for task scheduling in grid computing. Further CGOA keep away from catching non-global resources.

Here section II presents related work regarding parallel system architecture with its various models. Section III illustrates discussion of Cuckoo optimization and Genetic technique. Section IV explains proposed Cuckoo Genetic optimization algorithm. Vth section explores the performance evaluation with other related issues of parallel processing. Later, in section VI, conclusion and future work is discussed well.

• II.    Related Works

Ajith Abraham, Rajkumar Buyya and Baikunth Nath [3] have proposed computational grids and pursued by a concise explanation of three nature’s heuristics Simulated Annealing, Genetic Algorithm and Tabu Search. They additionally express hybridized practice of above algorithms which is useful in grid computational surroundings for task scheduling. In this paper, researchers attempt to address dynamic task scheduling to purely dispersed calculating sources. Conventional wisdom in arranging field has problem regarding scheduling which describe such affluence and variety that no lone scheduling process is enough. Heuristics derived from nature establish amazing degree of effectiveness and generality for managing combinatorial optimization efforts.

Fatos Xhafa and Ajith Abraham [4] have suggested this work, by reviewing some vital ideas from grid computing having scheduling dilemma and decision using heuristic and meta-heuristic methods. Problems regarding scheduling process are at the spirit of every grid related computational environment. Several categories of scheduling depend on dissimilar mechanisms like static vs. dynamic surroundings, multiobjectivity, adaptively are identified. Further heuristics and meta-heuristics techniques for scheduling in grids are accessible. They expose difficulty in scheduling with computational grids. The comparison in scheduling having conventional parallel and dispersed environment and demonstrates effectiveness of heuristics and metaheuristics methods for designing proficient grid schedulers.

Masoud Yaghini and Mohammad Rahim Akhavan Kazemzadeh [5] have presented a design and implementation methodology for meta-heuristic algorithms, named DIMMA. The proposed methodology contains three main stages and every stage has numerous steps in which performance that should be conceded out are clearly distinct in this paper. In addition, design and implementation of tabu search meta-heuristic for travelling salesman crisis is done as a case study to demonstrate availability of DIMMA. Meta- heuristic algorithms will gain extra and more status in the future as optimization trouble is rising in size and complication. In order to trace experiences and permit project to be simulated, a standard method as a methodology for designing and implementing meta-heuristic algorithms is essential. To the best of the authors’ knowledge, no methodology has been planned in literature for this purpose.

Jennifer M. Schopf [6] have proposed a common architecture for grid scheduling. Grid scheduler should create source selection decisions in surroundings. Here it has no organization above local sources. Further sources are dispersed and information regarding systems is frequently limited. Such connections are strongly tied for best working of grid information services. This grid scheduling method has three stages: resource discovery, system selection, and job execution.

Javier Carretero and Fatos Xhafa [7] have proposed GAs having schedulers for powerfully assigning tasks to sources in grid system. Scheduling is a key trouble in developing computational method, such as Grid and P2P, in order to promote from large calculating ability of such schemes. They present a general discussion on Genetic Algorithms for scheming proficient Grid schedulers that reduce the flow time and make span. Two encoding methods have been considered and most of GA mechanisms are executed and empirically studied. The extensive experimental revise showed that our GA-depend schedulers outperform existing GA implementations in the literature for the trouble and also exposed their effectiveness when makespan and flowtime are reduced either in a hierarchical or a simultaneous optimization form; preceding methods considered only the reduction of the makespan. Furthermore, they were capable to identify which GAs edition work finest in definite grid characteristics, which is extremely useful for real Grids. With the relationship of GA with heterogeneous processors in grid computing system creates fruitful outputs to optimize the results.

Lei Zhang, Yuehui Chen, Runyuan Sun, Shan Jing and Bo Yang [8] have projected heuristic approach on particle swarm optimization technique and is adapted for solving job scheduling dilemma in grid system. Every element characterized by probable key and location vector is replaced from continuous variable to discrete variable. It aspires for creation of an optimal schedule to get least conclusion time while finishing jobs. Solutions of simulated tests demonstrate the PSO algorithm that is capable to get enhanced schedule than GA.

P. Mathiyalagan, S.Suriya and Dr. S. N. Sivanandam [9] have projected this heuristic ant colony algorithm suits well for grid scheduling surroundings with stigmatic communication. Proposed ant colony algorithm in this paper has a customized pheromone updating regulation which resolves the grid scheduling trouble efficiently than that of the available ant colony algorithm. The grid computing system is a latest, powerful and inventive system for a set of heterogeneous dispersed computing systems. It needs grid scheduling to attain better presentation. The proficient scheduling of independent tasks in heterogeneous environment is main dilemma in grid computing. In common, discovering optimal schedule for such a surrounding using the traditional sequential technique is a NP-hard trouble whereas heuristic methods will offer near optimal solutions for compound troubles.

Raksha Sharma, Vishnu Kant Soni, Manoj Kumar Mishra, and Prachet Bhuyan [10] have proposed this objective of scheduling to get main feasible environment throughput and to equivalent function require having obtainable computing sources. Inspiration of review is to persuade leisure researcher in the field of grid computing. It identifies concept of scheduling and can set in building additional proficient scheduling mechanisms. Grid computing is a mode of dispersed computing. It engages managing, sharing of calculation power, data storage and network sources across active and geographically diffused association. As NP-complete is related with grid computing. So there is way out to select a suitable scheduling technique that is used in grid setting because of description of jobs, machines and network connectivity.

Pinky Rosemarry, Payal Singhal and Ravinder Singh [11] have proposed this to attain highest probable environment having maximum throughput and to equivalent function require with obtainable calculating sources. They will reconsider a variety of tasks and source scheduling mechanisms which will help to carry out further research in investigation. It engrosses sharing of sources having heterogeneous and geographically dispersed to resolve a variety of complex efforts and build up great scale application. As to expand requests, sources are necessary and so tasks and source scheduling become one of key search areas in grid calculating.

Xin-She Yang and Suash Deb [12] have proposed to formulate a new meta-heuristic method for optimization of problems known as Cuckoo Search. It is based on obligate brood parasitic performance of few cuckoo genus in mixture with levy flight performance of some birds and fruit flies. They authenticate proposed technique beside test utility and further compared its presentation with GA and PSO. At last, they converse the suggestion of the results and proposal for further research.

Jean-Paul Watson [13] has projected about local search. According to him local search techniques are always the most effective ways for searching the high-quality outputs to a wide range of combinatorial optimization problems that is to get the optimized results in job shop scheduling.

Liang Sun, Xiaochun Cheng and Yanchun Liang [14] propose the algorithm regarding selection procedure with hyper mutation values having a life span extended strategy. Thet adopted a special search procedure with an adaptive penalty function as the fitness function here and so this search gives the optimized results in both feasible and infeasible regions of the solution space.

Hedieh Sajedi and Maryam Rabiee [15] proposed for job scheduling. The examination takings in the framework of the well-known job-shop scheduling trouble, one of the hardest NP-hard problems come across in practice. The high volume of prior investigate on the job-shop scheduling trouble offers a varied range of obtainable algorithms and trouble occurrence, in addition to numerous empirical observations concerning local search algorithm behaviour; the latter are used to authenticate our behavioural forms.

J.C. Beck, T.K. Feng and J.P. Watson [16] have proposed this work; it represents a significant step toward a theory of local search. Using observed methods, they build up theoretical models of the performance of four well-known local search algorithms: a random walk, tabu search, iterated local search, and simulated annealing.

Liang Sun, Xiaochun Cheng, Yanchun Liang [17] have proposed GA with a penalty function for job shop scheduling. Here a clonal assortment depend hyper mutation and a life span extensive policy is planned. In this an adaptive penalty function is intended so that algorithm can explore in both feasible and infeasible regions of the solution space. Replicated trials were performed on 23 benchmark occasions taken from the OR-library and results demonstrate efficiency of planned mechanism.

Said Fathy El-Zoghdy [18] solves the load balancing with task migration problem in grid computing. Here a load balancing policy designed to handle the multiple tasks on heterogeneous cluster system in grid computing. A metric mean task response time minimize the response time and improves the load balancing in grid system.

Saeed Molaiy [21] develop a system to tackle task scheduling problem and proposed that task scheduling is a vital factor that improves the efficiency and performance in grid computing system by distributing the heterogeneous resources with the help of ant colony optimization technique.

• III.    Cuckoo Search and Genetic Approach

• A.    Cuckoo Search

Cuckoo search is an optimization mechanism developed by Xin-she Yang and Suash Deb [12]. Cuckoo was stimulated by necessitate clutch parasitism of few cuckoo species by laying their eggs in the nests of other host birds. Few host birds can connect through clash with interfering cuckoos. If a host bird discerns eggs are not their hold, it will either bowl these unknown eggs away its nest or build a new nest elsewhere. In cuckoo optimization, nests as resources, cuckoo as grid broker, and cuckoo egg as newly arrived tasks and the host’s eggs are considered as jobs in queue and characteristics of eggs are the constraints. If recently arrived task assures the restraints of tasks in possessions approximately, then task is selected for execution. Otherwise task is removed from that resource and some other best possible resource is preferred for that task. Following are the steps of proposed algorithm (CGOA – Cuckoo Genetic Optimization Algorithm) through which optimized best solution can be achieved:

• 1.    Using random particle cuckoo’s habitat is initialized and computed the value of random particles.

• 2.    Calculate ELR for each cuckoo as in equation (1) below:

• 3.    Cuckoo will lay egg in their subsequent space. This process will continue till required number of eggs lay down in the nest.

• 4.    Host birds recognize the eggs must be slayed and ensured that the security is in the full form.

• 5.    Eggs shade, chick mature and that creates one more optimized form of results.

• 6.  Estimate habitat of every recently grown-up

• 7.  Apply limit constraint on cuckoo’s maximum

• 8.    Cuckoos locate finest group and choose objective habitat and this help in finding fitness function.

• 9.    Allow new cuckoo population shift toward objective habitat that is another form of success.

• 10.    If condition met then its ending, otherwise go to step 2. It means the procedure is complete.

ELR = a*^* ( arr_ht * vrr_{Lo w})       (1)

ELR- Egg laying radius. NE- Current eggs numbers. TE- Eggs total number.

cuckoo.

number in surrounding. Also destroy all live in the pits habitats.

• B.    Genetic Mechanism

Genetic algorithm is the well known heuristic approach which is useful and efficient yet the problem is huge and difficult. Genetic algorithm supports the process of natural selection which means that “selects the best and discards the worst” to search a good result. Genetic algorithm begins with the population generation of solutions for the problem and performs evolution by repeatedly apply the set of genetic operators. GA starts from the generation of initiated population and further generated population has iterative evolution and crossover and mutations are two basic operations in each iteration used to create more generations. Further a objective function called fitness function computed in every iteration with each individual if currently generated population has better fitness value than the existing generated population. Further old one is replaced by new one population and it will continue till either n generation occurs or stopping criteria met [22]. The three search operators used in the genetic algorithm is selection, crossover and mutation operators that are significantly helped to obtain optimal solution.

Generally, GA consists of following components for getting the optimized solution:

Population is the primarily set used for this operation. A set of chromosome is said to be population. It is generated using random variables. It is used by the selection operator and further modified form be used for the crossover operator for swapping and mutation operator for the change in different form. Chromosome set creation is the major activity in this phase and so it is also called goal achieving phase.

Fitness function is the objective function. Fitness function has vital value here that is used to carry out the further operations. Fitness is computed for every chromosome to find exact optimal solution. With the help of fitness function, results can be achieved easily. Number of computations and logics are used to get the fitness value.

Selection is the basic criteria applied on the population. Selection is based on ranking metric. By analyzing the fitness of each chromosome, the chromosome which has the lowest fitness value will be replaced by another chromosome. Thus a new population is reformed. Selection is similar to selecting a cricket team from a list of country’s sports person’s population.

Crossover means swapping of the population data and applied after selection operation. Crossover operation takes place by interchanging the partial variables in the chromosome with each other using probability. This is used either at one point crossover or two point crossover.

Mutation operation is rarely used. Mutation is applied to preserve genetic diversity from one generation of a population of chromosomes to next one i.e. invert the randomly selected bits based on the mutation probability. Mutation is creation of different spices in the genetic approach.

• IV.    Proposed System

• A.    Cuckoo Genetic Algorithm

Cuckoo genetic algorithm is an amalgamation of COA and GA. Drawback of Genetic approach is to require reasonably long execution time to estimate and it have requirement to expand a trial to describe finest attributes. An additional drawback is its fast rate of transfer data among particles that increases possibility of being in a non-global optimal.

Solving redundancy and reliability in assigning the resources related problems via meta-heuristic algorithms has attracted increasing attention in recent years. A recently developed meta-heuristic optimization algorithm cuckoo search (CS) is hybridized with well-known genetic algorithm (GA) is proposed to solve the optimization of allocation dilemma. Embedding genetic operators in standard cuckoo search, the balance between the exploration and exploitation ability further improved and more search space are observed during the algorithms’ performance [19].

This proposed mechanism merges cuckoo search technique and Genetic approach to tackle the above mentioned weakness. CGOA is ruffled of two stages. First one obeys with cuckoo optimization and other one follows genetic approach. In CGOA at end of first stage, a population of cuckoo eggs in an area that has further most option for growth is feed to second stage as the initial population. At next stage of CGOA, one point crossover is consumed. Further, mutation will affect new population. With mutation a cuckoo is chosen erratically from population and it is reinstated by another one from population. Mutation process forms cuckoo population is called as new generation that gets best result is hoarded and so the process continue.

• B.    Job Scheduling using CGOA algorithm

Scheduling is the mechanism through which jobs specified having some meaning is to allocate resources which gives the final output as work done in complete form. The job may be virtual computation elements like threads, processes or data flows. Job scheduling in cuckoo search and genetic technique creates such strategy that gives the best optimal solution. The endeavour of CGOA for scheduling is current at best technique to allot tasks to clients to diminish completion time, resource efficiency, and increasing speed of convergence. CGOA is used in troubles with [15] complex hypothesis. This gives the efficient and accurate solutions. The steps are as follows:

Developing initial population:

Spawning initial population is pedestal of beginning in this approach. Population of cuckoos are recorded into a set of tasks. Every cell of habitat has mapped to possessions which are situated in process of every task.

Items arriving here, together with n, n is no. of job sets, j the no. of tasks (because every task set has many tasks), r is no. of resources, V n*r is order of tasks for every task set and time required for every task, this approach tries to search best result. It is assumed that no. of resources with no. of operations is equal: r=j .

Choose an optimal sequence of systems:

Sequence of run-time tasks on each resource is different. So for each job a[i]r*r, minimum execution time should be resulted. Nevertheless, presentation of a resource to do a task alone is not determinative, but all resources have minimum time to achieve a task with postulation that a resource should not be used more than once.

Calculation of Fitness Function:

Here this supposition that every task at any time can only execute on a system that existing one to one relationship between a system and operations of a task. So the fitness function used here satisfies the condition of the algorithm. To guarantee this conjecture and consequence coefficient which relate to fitness function ( FF 1 ) should be identified. Fitness function is defined by the equation (2):

FF_± = ХУ - ₁ m in(ET) + FL          (2)

Where j is no. of tasks, FL is penalty coefficient and ET is the execution time of tasks.

After getting the complete sequence of job then it is assigned to the resources by analyzing the load balance, execution time and transfer time.

Operations based on the input sequence:

Following manipulating execution time of tasks and judging best sequence of tasks on resources, allotment of resources be done based on input succession. Series of tasks be examined that is user will need to find which task to which system should be conveyed. Here, operation-based management is used to allot operation to resources. As every task precisely execute on every resource once, the no. of tasks accurately materializes to number of resource.

• V.    Performance Analysis

Performance of various aspects in scheduling jobs for parallel systems with the optimization of minimized make span time, minimized total transfer time and efficient load balance was analyzed. The analysis on the make span time, total transfer time and with efficient load balancing according to the optimization function with the given jobs schedule length.

As number of tools are available for designing and developing simulating scheduling techniques in grid computing system like SimGrid, Bricks, Gang Sim Arena, OptorSim, GridSim, Griddingcomp and Alea, but here the developed simulation is different and best from all. It has all the facilities for simulating and modelling all the events and operations in grid computing environments like handling heterogeneous resources, load balancing of recourses, help box of system users, applications in by simulating related with recourses management and to develop DAG between jobs and processors. It helps in designing and computing algorithm handling load balance. In order to compute the performance of proposed mechanism related with load balancing, a heterogeneous grid environment was built using different resource specifications. Note that the difference is only in case of Random Access Memory, the computing speed of central processor unit and the operating system used. This affects the performance of the system in the grid computing environment.

For the performance evaluation of CGOA, simulated heterogeneous computers or machines in the grid system is generated on the basis of given set of jobs, recourses and the number of processors or machines.

The experiment or system model is designed using MATLAB 13a version with advance optimization tool and initially the system resources and jobs are selected, where jobs are then divided into job sets and resources are then split into number of resource sets. In experimental work, 100 jobs are given that are subdivided into 14 job sets and 13 processors are divided into 100 resource sets where the goal is to optimize the best resources for the job sets using CGOA algorithm. All the simulation computations have been performed on a machine having core 2 duo processor (C2D), 3.9 GHz speed with 4GB as internal memory (RAM) and running on latest operating system Windows 8.1. The speed of bandwidth set as 50Mbps to 100Mbps and units are taken in seconds (as time unit).

The best schedule or way to solve the problem of any job scheduling or task scheduling is only the CGOA algorithm and its mechanism. It is the best as compared to the previously computed algorithms like ant colony algorithm or particle swarm optimization algorithm or simple genetic algorithm. So, to find the optimized schedule using CGOA algorithm, a comparison can be done and computed with the schedules obtained from other algorithms.

However, due to the combinatorial nature of the scheduling problem, it is very difficult and even impossible to find optimized schedule using CGOA mechanism for a very big scheduling problems (i.e., problems with multiple jobs or tasks with multiple processors).

To balance the load between the processor, a load balance technique is used in the parallel system or grid computing environment. Several techniques or approaches produce the best schedule length or minimum makespan having optimized results or solutions, but task balance or load balancing between tasks or jobs between heterogeneous machines or processors might not be satisfied in some of them. To avoid such type of situation or troubles, proposed mechanism or technique handles the load balance modifications with updated procedures between tasks and processors or nodes or machines to get the least schedule length (minimum makespan) and balance of load in task-processor relationship is fulfilled also.

Simulator compute the transmitting time of given job sets during load balancing operation between tasks and processors. Simulator passes through number of iterations with which required optimized results can be evaluated and so can get best solution.

Fig.1. Number of Job Sets and their Transfer Time

Fig. 1 here shows the number of job sets and their corresponding transfer time. These values are computed with the help of MATLAB simulator as above said. Here experiment applied having grid environment with cuckoo mechanism and genetic technique. This will create a relationship between given set of job sets and compute the transmitting time according to the given parameters.

The jobs are executed on the different processor in such a way that no duplication occurs during processing. This was setup in the simulator.

The term load balancing is defined as the total work divided in such a way that a machine or node or processor has to set up between two or more machines so that a large work be done in the given time period or interval and set the optimized way to get the best solution. This be done so that all the users get the fastest service facility.

Here Fig. 2 shows the no. of job sets and load balancing with resources. These values are computed from the MATLAB simulator by varying the job sets and according to the varied values.

Fig.2. Number of Job Sets and their Load Balancing

Fig.3. Number of Job Sets and their Execution Time

This is having different range of load balancing readings are computed. In this grid computing system, allocation of jobs and load balancing is important. If one of the processor or resource is often used (repetitive way) in this designed model or simulator, then there should be an imbalanced nature between resources or processors and jobs or job sets. This will create faulty results. So to avoid this problem, simulator operations was set up in such a way that no repetition occurs.

Execution time is the time consumed in execution of an algorithm for a given input on the set of parallel machines or on the set of grid computers. The execution time or make span time of the given job sets are shown in Fig. 3. The execution times of various job sets are differed due to their different kind of jobs hold by the job sets.

Finally concluding our performance work, in the future plan would like to analyze the system performance by their scalability and utilization of given resources with the number of varied job.

• VI.    Conclusion

Here CGOA solves task scheduling dilemma in grid environment is proposed. This technique precedes disadvantages of COA and GA. An execution of jobs based on Cuckoo-genetic (CGOA) algorithm with optimized scheduling of pair of job sets, by selecting the optimize resource and computing the minimum time for tasks execution on parallel computer systems or grid computing environment and resource sets are explored. From the effective design of our proposed system it is concluded that task scheduling produce the effective scheduling results in the parallel systems. The work focus is mainly on handling load balancing with minimized makespan time with less total transfer time. In future, the discussion would like to enlarge our optimization method to evaluate the parallel system for improving the scalability.

Acknowledgment

The author wishes to thank Prof. (Dr.) Karanjeet Singh Kahlon (Supervisor) and Prof. (Dr.) Gurvinder Singh (Co-Supervisor), both from Department of Computer Science, Guru Nanak Dev University, Amritsar (Punjab-India) for their valuable guidance and encouragement.