Steps Toward Computing Robust Schedules

September 2003

Steps Toward Computing Robust Schedules

Authors:

N. Policella, S. F. Smith, A. Cesta, and A. Oddi

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.
@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},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.