Reliability-Oriented Genetic Algorithm for Workflow Applications Using Max-Min Strategy

摘要

To optimize makespan and reliability for workflow applications, most existing works use list heuristics rather than genetic algorithms (GAs) which can usually give better solutions. In addition, most existing GAs evolve a scheduling solution randomly, which may give invalid solutions or lead to slow convergence of the algorithm. In this paper, we define three heuristics for GAs to decide the priorities for a resource and a task dynamically. We propose look-ahead genetic algorithm (LAGA) to optimize both makespan and reliability for workflow applications. It uses a novel evolution and evaluation mechanism: the genetic operators evolve the task-resource mapping for a scheduling solution, while the solutionpsilas task order is determined in the evaluation step using our new max-min strategy, which is specifically proposed for GAs. Our experiments show that LAGA can provide better solutions than existing list heuristics and evolve to better solutions more quickly than a traditional genetic algorithm.