Automatic construction of workflows on the Grid currently is a hot research topic. The problems that have to be solved are manifold: How can existing ser- vices be integrated into a workflow, that is able to ac- complish a specific task? How can an optimal workflow be constructed in respect to changing resource charac- teristics during the optimization process? How to cope with dynamically changing or incomplete knowledge of the goal function of the optimization process? - and fi nally: How to react to service failures during workflow execution?

In this paper we propose a method to optimize a workflow based on a heuristic A* approach that allows to react to dynamics in the environment, as changes in the Grid infrastructure and in the users requirements during the optimization process and failing resources during execution.