A Hybrid Genetic Algorithm and Variable Neighborhood Search for Task Scheduling Problem in Grid Environment
Sara Kardani Moghaddam, Farzad Khodadadi, Reza Entezari‐Maleki, Ali Movaghar · Procedia Engineering · 2012
This paper addresses scheduling problem of independent tasks in the market-based grid environment. In market-based grids, resource providers can charge users based on the amount of resource requested by them. In this case, scheduling algorithms should consider users’ willingness to execute their applications in most economical manner. As a solution to this problem, a hybrid genetic algorithm and variable neighborhood search is presented to reduce overall cost of task executions without noticeable increment in system makespan. Simulation results show that our algorithm performs much better than other algorithms in terms of cost of task executions. Considering the negative correlation between cost and makespan in grid environments, decrement in execution cost results in makespan increment. It should be mentioned that in the worst case, the makespan of the environment increased less than 17 percent which is tolerable, especially for users without any hard deadline on task executions.