Problems and Approaches of Workflow Scheduling in MediGRID

We describe four problems inherent to Grid scheduling that could be identified by means of measurements in the D-Grid. These problems make meta-scheduling nearly always a delicate task. In the face of this, we developed a new hybrid methodology to schedule application workflows which presumably supersedes existing methods. Our algorithm combines existing scheduling strategies for the Grid and for workflows, and it additionally employs three prediction methods for the expected queue waiting times. Three site scenarios could be identified where one respective prediction works best. To meet the dynamic characteristics of heterogeneous Grid resources, we use a list scheduling heuristic to perform full-ahead planning of workflow tasks based on execution time predictions, and then distribute Grid jobs just-in-time according to resource performance predictions calculated from up-to-date monitoring data.