For an application in public-resource computing environments, providing reliable scheduling based on resource reliability evaluation is becoming increasingly important. Most existing reputation models used for reliability evaluation ignore the time influence. And very few works use a robust genetic algorithm to optimize both time and reliability for a workflow application. Hence, in this paper, we propose the reliability-driven (RD) reputation, which is time dependent and can be used to evaluate a task’s reliability directly using the exponential failure model. Based on the RD reputation, we also propose Knowledge-Based Genetic Algorithm (KBGA) to optimize both time and reliability for a workflow application. KBGA uses heuristics to accelerate the evolution process without giving invalid solutions. Our experiments show that the RD reputation can improve the reliability of a workflow application with more accurate reputation, while the KBGA can evolve to better scheduling solutions more quickly than traditional genetic algorithms.