Independent Job Scheduling by Fuzzy C-Mean Clustering and an Ant Optimization Algorithm in a Computation Grid

摘要

Grid computing is gaining more significance in the high-performance computing world. This concept leads to the discovery of solutions for complicated problems regarding the diversity of available resources among different jobs in the Grid. However, the major problem is the optimal job scheduling for heterogeneous resources, in which each job needs to be allocated to a proper grid’s node with the appropriate resources. An important challenge is to solve optimally the scheduling problem, because the capability and availability of resources vary dynamically and the complexity of scheduling increases with the size of the grid. This paper, therefore, presents a framework which combines the Fuzzy C-Mean clustering with an Ant Colony Optimization (ACO) algorithm to improve the scheduling decision when the grid is heterogeneous. In the proposed model, the Fuzzy C-Mean algorithm classifies the jobs into appropriate classes, and the ACO algorithm maps the jobs to the appropriate resources. The ACO is characterized by ant-like mobile agents that cooperate and stochastically explore a network, iteratively building solutions based on their own memory and on the traces (pheromone levels) left by other agents. The simulation is done by using historical information on jobs in a grid. The experimental results show that the proposed algorithm can allocate jobs more efficiently and more effectively than the traditional algorithms for scheduling policies.