A quadratic edge-finding filtering algorithm for cumulative resource constraints
Tóm tắt
The cumulative scheduling constraint, which enforces the sharing of a finite resource by several tasks, is widely used in constraint-based scheduling applications. Propagation of the cumulative constraint can be performed by several different filtering algorithms, often used in combination. One of the most important and successful of these filtering algorithms is edge-finding. Recent work by Vilím has resulted in a 𝒪 (kn log n) algorithm for cumulative edge-finding (where n is the number of tasks and k is the number of distinct capacity requirements), as well as a new related filter, timetable edge-finding, with a complexity of 𝒪(n
2). We present a sound 𝒪(n
2) filtering algorithm for standard cumulative edge-finding, orthogonal to the work of Vilím; we also show how this algorithm’s filtering may be improved by incorporating some reasoning from extended edge-finding, with no increase in complexity. The complexity of the new algorithm does not strictly dominate previous edge-finders for small k, and it sometimes requires more iterations to reach the same fixpoint; nevertheless, results from Project Scheduling Problem Library benchmarks show that in practice this algorithm consistently outperforms earlier edge-finding filters, and remains competitive with timetable edge-finding, despite the latter algorithm’s generally stronger filtering.
Tài liệu tham khảo
Aggoun, A., & Beldiceanu, N. (1993). Extending CHIP in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17(7), 57–73.
Baptiste, P., & Le Pape, C. (2000). Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 5(1), 119–139.
Baptiste, P., Le Pape, C., Nuijten, W.P.M. (2001). Constraint-based scheduling: applying constraint programming to scheduling problems. Berlin: Springer.
Carlier, J., & Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146–161.
Caseau, Y., & Laburthe, F. (1994). Improved CLP scheduling with task intervals. In P. Van Hentenryck (Ed). ICLP 1994—logic programming (pp. 369–383). Cambridge: MIT Press.
Gecode. http://www.gecode.org. Accessed 30 Aug 2012.
Kameugne, R., & Fotso, L.P. (2013). A cumulative not-first/not-last filtering algorithm in \(\mathcal {O}(n^{2}\log (n))\). Indian Journal of Pure Applied Mathematics, 44(1), 95–115 Springer, Berlin. doi:10.1007/s13226-013-0005-z.
Kameugne, R., Fotso, L.P., Scott, J., Ngo-Kateu, Y. (2011). A quadratic edge-finding filtering algorithm for cumulative resource constraints. In J.H.M. Lee (Ed.), CP 2011—principles and practice of constraint programming, LNCS (Vol. 6876, pp. 478–492). Berlin: Springer.
Kolisch, R., & Sprecher, A. (1996). PSPLIB–a project scheduling library. European Journal of Operational Research, 96, 205–216.
Mercier, L., & Van Hentenryck, P. (2008). Edge finding for cumulative scheduling. INFORMS Journal on Computing, 20(1), 143–153.
Nuijten, W.P.M. (1994). Time and resource constrained scheduling. PhD thesis. Technische Universiteit Eindhoven.
PSPLib—project scheduling problem library. http://129.187.106.231/psplib/.
Schulte, C., Tack, G., Lagerkvist, M.Z. (2012). Modeling. In C. Schulte, G. Tack, M.Z. Lagerkvist (Eds.), Modeling and programming with Gecode. Corresponds to Gecode 3.7.3.
Schutt, A., & Wolf, A. (2010). A new O(n 2 log n) not-first/not-last pruning algorithm for cumulative resource constraint. In D. Cohen (Ed.), CP 2010—principles and practice of constraint programming, LNCS (Vol. 6308, pp. 445–459). Berlin: Springer.
Scott, J. (2010). Filtering algorithms for discrete cumulative resources. Masters Thesis, Uppsala University, Sweden. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-132172.
Vilím, P. (2007). Global constraints in scheduling. PhD thesis, Charles University in Prague.
Vilím, P. (2009). Edge finding filtering algorithm for discrete cumulative resources in \(O(kn \log n)\). In I.P. Gent (Ed.), CP 2009—principles and practice of constraint programming, LNCS (Vol. 5732, pp. 802–816). Berlin: Springer.
Vilím, P. (2009). Max energy filtering algorithm for discrete cumulative resources. In W.J. van Hoeve, & J.N. Hooker (Eds.), CPAIOR 2009—integration of AI and OR techniques in constraint programming, LNCS (Vol. 5547, pp. 294–308). Berlin: Springer.
Vilím, P. (2011). Timetable edge finding filtering algorithm for discrete cumulative resources. In T. Achterberg & J.C. Beck (Eds.), CPAIOR 2011—integration of AI and OR techniques in constraint programming, LNCS (Vol. 6697, pp. 230–245). Berlin: Springer.
Wolf, A., & Schrader, G. (2006). O(nlog n) overload checking for the cumulative constraint and its application. In M. Umeda, A. Wolf, O. Bartenstein, U. Geske, D. Seipel, O. Takata (Eds.), INAP 2005—applications of declarative programming for knowledge management, LNCS (Vol. 4369, pp. 88–101). Berlin: Springer.