A Precedence Constraint Posting Approach

This chapter summarizes some previous work on a constraint-based scheduling approach effectively applied to Resource-Constrained Project Scheduling problems. The approach is based on a formulation of the problem as a Constraint Satisfaction Problem (CSP). In particular the problem is reduced to the one of establishing sufficient precedence constraints between activities that require the same resource so as to eliminate all possible resource contention, defining what is called the Precedence Constraint Posting (PCP) approach. The PCP scheduling approach has two attractive properties: first it operates in a search space that avoids over-commitment to specific activity start times, and can be more efficiently searched; second, the solution generated is a so-called "flexible schedule", designating a set of acceptable futures, which provides a basis for efficiently responding to unexpected disruptions during execution. This chapter summarizes a body of work developed over the years on PCP-based scheduling to take advantage of such properties. In particular, the chapter presents an overview on a number of original algorithms for efficiently finding a solution to a scheduling problem, for generating robust schedules, and for searching near-optimal makespan solutions.

Tipo Pubblicazione: 
Contributo in volume
Author or Creator: 
Cesta, Amedeo
Oddi, Angelo
Policella, Nicola
Smith, Stephen F.
Springer International Publishing AG, Berlin, DEU
Handbook on Project Management and Scheduling Vol.1, edited by Schwindt, Christoph; Zimmermann, Jürgen, pp. 113–133. Berlin: Springer International Publishing AG, 2015
Resource Identifier: 
ISTC Author: 
Ritratto di Angelo Oddi
Real name: 
Ritratto di Amedeo Cesta
Real name: