Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm

For applications in large-scale distributed systems, it is becoming increasingly important to provide reliable scheduling by evaluating the reliability of resources. However, most existing reputation models used for reliability evaluation ignore the critical influence of task runtime. In addition, most previous work uses list heuristics to optimize the makespan and reliability of workflow applications instead of genetic algorithms (GAs), which can give several satisfying solutions for choice. Hence, in this paper, we first propose the reliability-driven (RD) reputation, which is time dependent, and can be used to effectively evaluate the reliability of a resource in widely distributed systems. We then propose a look-ahead genetic algorithm (LAGA) which utilizes the RD reputation to optimize both the makespan and the reliability of a workflow application. The LAGA uses a novel evolution and evaluation mechanism: (i) the evolution operators evolve the task-resource mapping of a scheduling solution and (ii) the evaluation step determines the task order of solutions by using our proposed max-min strategy, which is the first two-phase strategy that can work with GAs. Our experiments show that the RD reputation improves the reliability of an application with more accurate reputations, while the LAGA provides better solutions than existing list heuristics and evolves to better solutions more quickly than a traditional GA. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.