Chemical Reaction Optimization For Task Scheduling In Grid

Grid computing is a new distributed computing model along with the rapiddevelopment of internet technology. Through the internet, distributed computingresources are combined as a super-computer to solve problems with massive complexcalculations. The task scheduling is the core of grid computing. Efficient taskscheduling algorithm can take advantage of the computing resources in the gridsystem, so as to achieve the best overall system performance. However, due to thecomputing resources with characteristics of distribution, heterogeneity and dynamism,the task scheduling problems in grid become extremely difficult and complex.Therefore, how to develop efficient task scheduling algorithms is a great challengethat grid computing is facing.Some effective scheduling strategies have been developed for task schedulingproblems now, such as HEFT algorithm based on list scheduling and GeneticAlgorithm, Ant Colony Optimization, Simulated Annealing, Taboo Search based onrandom search. These algorithms have both advantages and disadvantages on taskscheduling, and task scheduling has been proven to be NP-hard problem. So we canusually approximate the best solutions with them. The huge types of schedulingproblem and the small number of generally acknowledged methods mean that moremethods are needed.The paper introduces the concept, characteristics and objectives of the taskscheduling in grid. Meanwhile, scheduling methods are classified and described indetail. For the dependent tasks which are the most common ones in grid, weintroduced its DAG mathematical model, and a new task scheduling algorithm named"CROTS" is put forward. The algorithm consists of two elements: An intelligentapproach to assign the execution orders of tasks by task level, and an allocationalgorithm based on chemical-reaction-inspired(CRO) meta-heuristic to map tasks toprocessors. CRO is a meta-heuristic by mimicking the interactions of molecules in achemical reaction to reach a low energy stable state. The core of CRO is fourelementary reactions: On-wall Ineffective Collision, Decomposition, Inter-molecularIneffective Collision and Synthesis. Decomposition reaction broadens the searchspace effectively, so it avoids that the algorithm gets some local optimum. CROTStakes the advantage of CRO sufficiently, and it uses an intelligent method for task listsearching, so improves the possibility of getting the global optimum. The experimentsshow that the CRO-based algorithm performs consistently better than HEFT and CPOP without incurring much computational cost. Meanwhile, CRO is more suitablefor large-scale problems.