×

A cumulative not-first/not-last filtering algorithm in \(O(n^2 \log(n))\). (English) Zbl 1282.90070

Summary: In cumulative and disjunctive constraint-based scheduling, the resource constraint is enforced by several filtering rules. Among these rules, we have (extended) edge-finding and not-first/not-last rules. The not-first/not-last rule detects tasks that cannot run first/last relatively to a set of tasks and prunes their time bounds. In this paper, it is presented a sound \(O(n^2 \log(n))\) algorithm for the cumulative not-first/not-last rule where \(n\) is the number of tasks. This algorithm reaches the same fix point as previous not-first/not-last algorithms, although it may take additional iterations to do so. The worst case complexity of this new algorithm for the maximal adjustment is the same as our previous complete \(O(n^2|H| \log n)\) not-first/not-last algorithm [the authors, “A Complete Filtering Algorithm for Cumulative Not-First/Not-Last rule in \(O(n^2|H| \log n)\)”, in: Proceeding of CSCLP 2010, Berlin, Germany, 31–42 (2010)] where \(|H|\) is the maximum between the number of distinct earliest completion and latest start times of tasks. But, experimental results on benchmarks from the Project Scheduling Problem Library (PSPLib) and the Baptiste and Le Pape data set (BL) suggest that the new not-first/not-last algorithm has a substantially reduced runtime. Furthermore, the results demonstrate that in practice the new algorithm rarely requires more propagations than previous not-first/not-last algorithms.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R Baptiste and C. Le Pape, Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems, Con-straints, 5(1) (2000), 119–139. · Zbl 0941.90030
[2] R Baptiste, C. Le Pape and W. Nuijten, Constraint-based scheduling: applying constraint programming to scheduling problems. Kluwer, Boston (2001). · Zbl 1094.90002
[3] Y. Caseau and F. Laburthe, Improved CLP scheduling with task intervals, In P. A preliminary version of this paper was accepted to CPDP 2010 [5], Van Hentenryck (Ed.), ICLP1994–Logic Programming, MIT Press, Boston (1994), 369–383.
[4] Gecode, a generic constraint development environment. Available from urlhttp://www.gecode.org . Accessed 30 August, (2010).
[5] R. Kameugne and L. P. Fotso, A not-first/not-last algorithm for cumulative resource in O(n 2 log n), Accepted to CPDP 2010 Doctoral Program, St Andrews, Scotland (2010).
[6] R. Kameugne, E. Kouakam and L. P. Fotso, La Condition Not-First/Not-Last en Ordonnancement Cumulatif, In proceeding of ROADEF 2010, Toulouse, France (2010), 89–97.
[7] R. Kameugne and L. P. Fotso, A Complete Filtering Algorithm for Cumulative Not-First/Not-Last rule in O(n 2 |H| log n), In Proceeding of CSCLP 2010, Berlin, Germany, (2010), 31–42. · Zbl 1282.90070
[8] R. Kameugne, L. P. Fotso, J. Scott and Y. Ngo-Kateu, A Quadratic Edge-Finding Filtering Algorithm for Cumulative Resource Constraints, In: Lee, J. (ed.) CP 2011, LNCS vol. 6876, Springer, Heidelberg (2011), 478–492. · Zbl 1314.90038
[9] R. Kolisch and A. Sprecher, PSPLIB – A project scheduling problem library, Euro-pean Journal of Operational Research, 96(1) (1997), 205–216. · Zbl 0947.90587
[10] P. Torres and P. Lopez, On Not-First/Not-Last Conditions in Disjunctive Scheduling, European Journal of Operational Research, 127(2) (2000), 332–343. · Zbl 0990.90049
[11] L. Mercier and P. Van Hentenryck, Edge finding for cumulative scheduling, IN-FORMS Journal on Computing 20(1), (2008), 143–153. · Zbl 1243.90068
[12] W. Nuijten, Time and resource constrained scheduling: a constraint satisfaction approach, PhD thesis, Eindhoven University of Technology. (1994). · Zbl 0837.90068
[13] A. Schutt and A. Wolf, A New O(n 2 log n) Not-First/Not-Last Pruning Algorithm for Cumulative Resource Constraints, In: Cohen, D. (ed.) CP 2010, LNCS vol. 6308, Springer, Heidelberg (2010), 445–459.
[14] A. Schutt, A. Wolf and G. Schrader, Not-first and Not-last Detection for Cumulative Scheduling in O(n 3 log n), In Proceedings 16th International Conference on Appli-cations of Declarative Programming and Knowledge, INAP 2005, Fukuoka, Japan, (2005), 66–80.
[15] P. Vilím, Global constraints in scheduling, PhD thesis, Charles University, Prague, (2007).
[16] P. Vilím, Max energy filtering algorithm for discrete cumulative resources, In.van Hoeve, W.J., Hooker, J.N.(eds) CPAIOR 2009, LNCS, vol. 5547, Springer, Heidel-berg (2009), 66–80.
[17] P. Vilím, Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Re-sources. In: van Hoeve, W.J., Hooker, J.N. (eds) CPAIOR 2011, LNCS, Volume 6697, Springer, Heidelberg (2011), 230–245. · Zbl 1302.90090
[18] P. Vilím, Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n). In: Gent, I.P. (ed) CP 2009, LNCS, vol. 5732. Springer, Heidelberg (2009), 802–816.
[19] A. Wolf and G. Schrader, O(n log n) overload checking for the cumulative con-straint and its application, In: Umeda, M., et al. (eds) INAP 2005, LNCS, vol. 4369, Springer, Heidelberg (2005), 88–101.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.