Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints
- 1 Department of Mathematics, Higher Teachers’ Training College, University of Maroua, Maroua, Cameroon；Department of Mathematics, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon
- 2 Department of Computer Sciences, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon
- 3 Department of Computer Sciences, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon
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 3 ） time-intervals to be considered (where n is the nu mber of tasks). In order to reduce the number of time-intervals in the energetic reasoning, the maxi mum 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 3 ） . 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.
- 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
- 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
- P. Baptiste, “Resource Constraints for Preemptive and Non-Preemptive Scheduling,” DEA, Informatique et Recherche Operationnelle, University of Paris VI, Institut Blaise Pascal, 1995.
- 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
- 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.
- R. Kameugne and L. P. Fotso, “Energetic Edge-Finder for Cumulative Resource Constraint,” Proceeding of CPDP 2009 Doctoral Program, Lisbone, 2009, pp. 54-63.
- 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
- 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.
- “PSPLib—Project Scheduling Problem Li-brary,” http://129.187.106.231/psplib
- 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
- 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.
- 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