AAAI Publications, Twenty-Third International Conference on Automated Planning and Scheduling

Font Size: 
A Min-Flow Algorithm for Minimal Critical Set Detection in Resource Constrained Project Scheduling
Michele Lombardi, Michela Milano

Last modified: 2013-06-02


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.


Resource Constrained Project Scheduling; Precedence Constraint Posting; Minimal Critical Set

Full Text: PDF