Share This Article:

Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints

Abstract Full-Text HTML Download Download as PDF (Size:282KB) PP. 589-600
DOI: 10.4236/ajor.2013.36056    2,926 Downloads   4,295 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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.

References

[1] P. Baptiste, C. Le Pape and W. P. M. Nuijten, “Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems,” Springer, Berlin, 2001.
http://dx.doi.org/10.1007/978-1-4615-1479-4
[2] A. Aggoun and N. Beldiceanu, “Extending CHIP in Order to Solve Complex Scheduling and Placement Problems,” Mathematical and Computer Modelling, Vol. 17, No. 7, 1993, pp. 57-73.
http://dx.doi.org/10.1016/0895-7177(93)90068-A
[3] P. Baptiste, “Resource Constraints for Preemptive and Non-Preemptive Scheduling,” DEA, Informatique et Recherche Operationnelle, University of Paris VI, Institut Blaise Pascal, 1995.
[4] L. Mercier and P. Van Hentenryck, “Edge Finding for Cumulative Scheduling,” INFORMS Journal on Computing, Vol. 20, No. 1, 2008, pp. 143-153.
http://dx.doi.org/10.1287/ijoc.1070.0226
[5] S. F. Betmbe, “Energetic Edge Finder: Algorithme de Propagation de la Contrainte de Ressource Cumulative,” Master 2 en Infor-matique, Université de Yaoundé 1, 2012.
[6] R. Kameugne and L. P. Fotso, “Energetic Edge-Finder for Cumulative Resource Constraint,” Proceeding of CPDP 2009 Doctoral Program, Lisbone, 2009, pp. 54-63.
[7] R. Kameugne, L. P. Fotso, J. Scott and Y. Ngo-Kateu, “A Quadratic Edge-Finding Filtering Algorithm for Cumulative Resource Constraints,” In: J. H. M. Lee, Ed., CP 2011—Principles and Practice of Constraint Programming, Springer, Berlin, 2011, pp. 478-492.
http://dx.doi.org/10.1007/978-3-642-23786-7_37
[8] R. Kameugne, L. P. Fotso, J. Scott and Y. Ngo-Kateu, “A Quadratic Edge-Finding Filtering Algorithm for Cumulative Resource Constraints,” Extended Version of the CP 2011 Paper, Constraints, Forthcoming, 2013.
[9] “PSPLib—Project Scheduling Problem Li-brary,”
http://129.187.106.231/psplib
[10] P. Baptiste and C. Le Pape, “Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems,” Constraints, Vol. 5, No. 1, 2000, pp. 119-139.
http://dx.doi.org/10.1023/A:1009822502231
[11] R. Kameugne, L. P. Fotso and J. Scott, “A Quadratic Extended Edge-Finding Filtering Algorithm for Cumulative Resource Constraints,” International Journal of Planning and Scheduling, Forthcoming, 2013.
[12] P. Vilm, “Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources,” In: T. Achterberg and J. C. Beck, Eds., CPAIOR 2011—Integration of AI and OR Techniques in Constraint Programming, Springer, Berlin, 2011, pp. 230-245.
http://dx.doi.org/10.1007/978-3-642-21311-3_22
[13] P. Ouellet and C.-G. Quimper, “Time-Table Extended-Edge-Finding for the Cumulative Constraint,” Accepted to CP 2013, 2013.
[14] R. Kameugne and L. P. Fotso, “A Cumulative Not-First/ Not-Last Filtering Algorithm in O(n2logn),” Indian Journal of Pure and Applied Mathematics, Vol. 44, No. 1, 2013, pp. 95-115.
http://dx.doi.org/10.1007/s13226-013-0005-z
[15] A. Schutt and A. Wolf, “A New O(n2logn) Not-First/ Not-Last Pruning Algorithm for Cumulative Resource Con-straints,” In: D. Cohen, Ed., CP 2010—Principles and Practice of Constraint Programming, Springer, Berlin, 2010, pp. 445-459.
http://dx.doi.org/10.1007/978-3-642-15396-9_36
[16] T. Berthold, S. Heinz and J. Schulz, “An Approximative Criterion for the Potential of Energetic Reasoning,” In: A. Marchetti-Spaccamela and M. Segal, Eds., Theory and Practice of Algorithms in (Computer) Systems, Springer, Berlin, 2011, pp. 229-239.
http://dx.doi.org/10.1007/978-3-642-19754-3_23
[17] S. Heinz and J. Schulz, “Explanations for the Cumulative Constraint: An Experimental Study,” In: P. M. Pardalos and S. Rebennack, Eds., Experimental Algorithms, Springer, Berlin, 2011, pp. 400-409.
http://dx.doi.org/10.1007/978-3-642-20662-7_34
[18] A. Schutt, T. Feydy and P. J. Stuckey, “Explaining TimeTable-Edge-Finding Propagation for the Cumulative Re-source Constraint,” CPAIOR 2011—Integration of AI and OR Techniques in Constraint Programming, 2013, pp. 234-250.
[19] P. Vilm, “Max Energy Filtering Algorithm for Discrete Cumulative Resources,” In: W. J. van Hoeve and J. N. Hooker, Eds., CPAIOR 2009—Integration of AI and OR Tech-niques in Constraint Programming, Springer, Berlin, 2009, pp. 294-308.
http://dx.doi.org/10.1007/978-3-642-01929-6_22
[20] 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
[21] 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
[22] Y. Caseau and F. Laburthe, “Improved CLP Scheduling with Task Intervals,” In: P. Van Hentenryck, Ed., ICLP 1994—Logic Programming, MIT Press, Cambridge, 1994, pp. 369-383.
[23] Gecode, 2012. http://www.gecode.org

  
comments powered by Disqus

Copyright © 2019 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.