Robust scheduling of metaprograms

Scheduling coarse-grain tasks, e.g. metaprograms on a grid, uses estimation of the execution times of individual components to compute optimal schedules. Various factors (hazards) lead to estimation errors, which affect both the performance of the schedule and its resource utilization. We introduce the concept of robustness of a schedule and present an analysis technique to determine the chance that a metaprogram exceeds its execution time due to components outside its critical path. The results of this analysis are used to compute schedules less sensitive to hazards. This translates into more accurate reservation requirements for critical systems, and reduced expected execution time for noncritical metaprograms executed repeatedly. We introduce the concept of the entropy of a schedule and conjecture that a more robust schedule is one that minimizes the entropy of a schedule. Copyright (C) 2002 John Wiley Sons, Ltd.