Steps Toward Computing Robust Schedules

Abstract

In this paper we consider the problem of building schedules that retain temporal flexibility. Such a feature represents a relevant benefit for managing changes in a dynamic environment. We begin by formalizing the concept of flexibility, to provide a set of metrics against which the flexibility of competing schedules can be compared. Then, using a common solving framework, we develop two orthogonal procedures for constructing a flexible schedule. The first, which we call the resource envelope based approach, uses computed bounds on cumulative resource usage (i.e., a resource envelope) to identify 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 generalizes this solution to a set of resource feasible solutions. We evaluate the relative effectiveness of these two procedures on a set of project scheduling benchmark problems, considering both their problem solving performance and the flexibility of the solutions they generate.