A Min-Flow Algorithm for Minimal Critical Set Detection in Resource Constrained Project Scheduling

Abstract

This is a summary of Lombardi and Milano, 2012, where we propose a novel method for Minimal Critical Set identification, to be used for the solution of scheduling problems via Precedence Constraint Posting. The method is based on a minimum-flow problem and a heuristic minimization step. The proposed approach is much more scalable than enumeration-based MCS detection, faster and easier to implement than enveloped-based sampling, more versatile than earliest-start-schedule sampling. As a second major contribution, the paper contains a thorough comparison (on the PSPLIB) of MCS detection method, which outlines their individual strengths and weakness. Additionally, the experimentation provides novel insight in the effectiveness of a widely employed MCS ranking heuristic.