Generating robust schedules through temporal flexibility

This paper considers the problem of generating partial or-der schedules (POS), that is, schedules which retain tempo-ral flexibility and thus provide some degree of robustness in the face of unpredictable execution circumstances. We begin by proposing a set of measures for assessing and comparing the robustness properties of alternative POSs. Then, using a common solving framework, we develop two orthogonal pro-cedures for constructing a POS. The first, which we call the resource envelope based approach, uses computed bounds on cumulative resource usage (i.e., a resource envelope) to iden-tify potential resource conflicts, and progressively winnows the total set of temporally feasible solutions into a smaller set of resource feasible solutions by resolving detected conflicts. The second, referred to as the earliest start time approach, instead uses conflict analysis of a specific (i.e., earliest start time) solution to generate an initial fixed-time schedule, and then expands this solution to a set of resource feasible solu-tions in a post-processing step. We evaluate the relative effec-tiveness of these two procedures on a set of project schedul-ing benchmark problems. As might be expected, the second approach, by virtue of its more focused analysis, is found to be a more efficient POS generator. Somewhat counterintu-itively, however, it is also found to produce POSs that are more robust