Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints

HTML  Download Download as PDF (Size: 282KB)  PP. 589-600  
DOI: 10.4236/ajor.2013.36056    3,389 Downloads   5,068 Views  Citations

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.

Share and Cite:

R. Kameugne, S. Fetgo and L. Fotso, "Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints," American Journal of Operations Research, Vol. 3 No. 6, 2013, pp. 589-600. doi: 10.4236/ajor.2013.36056.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.