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.
BibTeX
@workshop{Policella-2003-120527,author = {N. Policella and S. F. Smith and A. Cesta and A. Oddi},
title = {Steps Toward Computing Robust Schedules},
booktitle = {Proceedings of CP '03 3rd International Workshop on Online Constraint Solving: Handling Change and Uncertainty},
year = {2003},
month = {September},
}