Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints

Roger Kameugne, Sévérine Betmbe Fetgo, Laure Pauline Fotso

Department of Computer Sciences, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon.
Department of Mathematics, Higher Teachers’ Training College, University of Maroua, Maroua, Cameroon；Department of Mathematics, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon.

DOI: 10.4236/ajor.2013.36056                

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（n³） 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（n³）. 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.

Keywords

Constraint-Based Scheduling; Global Constraint; Cumulative Resource; Energetic Reasoning; Edge-Finding; Extended Edge-Finding; Maximum Density; Minimum Slack

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