A Precedence Constraint Posting Approach for the RCPSP with Time Lags and Variable Durations

Abstract. Resource Constrained Project Scheduling Problem is a very important problem in project management, manufacturing and resource optimization. We focus on a variant of RCPSP with time lags and vari-able activity durations. The solving approach is based on Precedence Constraint Posting that adds new precedence constraints to the original project graph so that all resource conflicts are solved and a consistent assignment of start times can be computed for whatever combination of activity durations. We propose a novel method for computing resource conflicts based on the minimum flow on the resource graph and we use it in an efficient complete search strategy. We experiment the approach on instances coming from the scheduling of parallel applications on multi processor systems on chip.