TITLE:
Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints
AUTHORS:
Roger Kameugne, Sévérine Betmbe Fetgo, Laure Pauline Fotso
KEYWORDS:
Constraint-Based Scheduling; Global Constraint; Cumulative Resource; Energetic Reasoning; Edge-Finding; Extended Edge-Finding; Maximum Density; Minimum Slack
JOURNAL NAME:
American Journal of Operations Research,
Vol.3 No.6,
November
29,
2013
ABSTRACT:
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.