Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints

• 作者: Laure Pauline Fotso Roger Kameugne Sévérine Betmbe Fetgo
• 来源期刊: 美国运筹学期刊(英文)
• 学科: 医学
• 关键词: Constraint-Based Scheduling Global CONSTRAINT CUMULATIVE Resource ENERGETIC REASONING Edge-Finding EXTENDED Edge-Finding Maximum Density Minimum SLACK
• 年，卷（期）: 2013,（6）
• 页码范围: 589-600
• 页数: 12页
• 分类号: R73

摘要

Edge-finding and energetic reasoning are well known filtering rules used in constraint based disjunctive and cumulative scheduling during the propagation of the resource constraint. In practice, however, edge-finding is most used (because it has a low running time complexity) than the energetic reasoning which needs O(n3) time-intervals to be considered (where n is the number of tasks). In order to reduce the number of time-intervals in the energetic reasoning, the maximum density and the minimum slack notions are used as criteria to select the time-intervals. The paper proposes a new filtering algorithm for cumulative resource constraint, and titled energetic extended edge finder of complexity O(n3). The new algorithm is a hybridization of extended edge-finding and energetic reasoning: more powerful than the extended edge-finding and faster than the energetic reasoning. It is proven that the new algorithm subsumes the extended edge-finding algorithm. Results on Resource Constrained Project Scheduling Problems (RCPSP) from BL set and PSPLib librairies are reported. These results show that in practice the new algorithm is a good trade-off between the filtering power and the running time on instances where the number of tasks is less than 30.