Article citationsMore>>

P. Vilm, “Edge Finding Filtering Algorithm for Discrete Cumula-tive Resources in O(knlogn),” In: I. P. Gent, Ed., CP 2009—Principles and Practice of Constraint Programming, Springer, Berlin, 2009, pp. 802-816.
http://dx.doi.org/10.1007/978-3-642-04244-7_62

has been cited by the following article:

• 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.