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

Book One

Volume

Proceedings of the International Conference on Automated Planning and Scheduling, 23

Journal Presentation Track

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.

10.1609/icaps.v23i1.13580