Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints

DOI: 10.4236/ajor.2013.36056   PDF   HTML     3,060 Downloads   4,441 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.

Conflicts of Interest

The authors declare no conflicts of interest.

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 © 2020 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.