A min-flow algorithm for Minimal Critical Set detection in Resource Constrained Project Scheduling

作者：Lombardi Michele; Milano Michela^*

来源：Artificial Intelligence, 2012, 182: 58-67.

DOI：10.1016/j.artint.2011.12.001

• Constraint-based scheduling
• Constraint programming
• Precedence Constraint Posting
• Minimal Critical Set
• Min-flow algorithm

We propose a min-flow algorithm for detecting Minimal Critical Sets (MCS) in Resource Constrained Project Scheduling Problems (RCPSP). The MCS detection is a fundamental step in the Precedence Constraint Posting method (PCP), one of the most successful approaches for the RCPSP. The proposed approach is considerably simpler compared to existing flow based MCS detection procedures and has better scalability compared to enumeration- and envelope-based ones, while still providing good quality Critical Sets. The method is suitable for problem variants with generalized precedence relations or uncertain/variable durations.

• 出版日期2012-5