Proceedings CP-03 Workshop on Online Constraint Solving: Handling Change and Uncertainty, Cork Ireland, September 29, 2003

Steps toward Computing Flexible Schedules

Nicola Policella(1), Stephen F. Smith(2), Amedeo Cesta (1) and Angelo Oddi(1)

(1) IP-CNR
National Research Council
Viale Marx 15
I-00137 Rome, Italy

(2)The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA


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.
Copyright 2003, Policella, Smith, Cesta and Oddi. All rights reserved.
Full paper in .pdf format