Article citationsMore>>

A. Wolf and G. Schrader, “O(nlogn) Overload Checking for the Cumulative Constraint and Its Application,” In: M. Umeda, A. Wolf, O. Bartenstein, U. Geske, D. Seipel and O. Takata, Eds., INAP 2005—Applications of Declarative Pro-gramming for Knowledge Management, Springer, Berlin, 2006, pp. 88-101.
http://dx.doi.org/10.1007/11963578_8

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.