Title: A quadratic extended edge-finding filtering algorithm for cumulative resource constraints

Authors: Roger Kameugne; Laure Pauline Fotso; Joseph Scott

Addresses: Department of Mathematics, Higher Teachers' Training College, University of Maroua, P.O. Box 1045, Maroua, Cameroon; Department of Mathematics, Faculty of Sciences, University of Yaoundé I, P.O. Box 812, Yaoundé, Cameroon ' Department of Computer Sciences, Faculty of Sciences, University of Yaoundé I, P.O. Box 812, Yaoundé, Cameroon ' Computing Science Division, Department of Information Technology, Uppsala University, P.O. Box 337, SE-751 05, Uppsala, Sweden

Abstract: Edge-finding, extended edge-finding, not-first/not-last and energetic reasoning are well-known filtering rules used in constraint-based scheduling problems for propagating constraints over disjunctive and cumulative resources. In practice, these filtering algorithms frequently form part of a sequence to form a more powerful propagator, thereby helping to reduce search tree size. In this paper, we propose a sound O(n²) extended edge-finding algorithm for cumulative resources, where n is the number of tasks sharing the resource. This algorithm uses the notion of minimum slack to detect when extended edge-finding justifies a strengthening of a domain, and it is more efficacious when executed on a domain already at the fix point of standard edge-finding. Previously, the best known complexity for filtering extended edge-finding on cumulative resources was O(kn²) (where k is the number of distinct capacity requirements). Experimental results on resource constrained scheduling benchmarks confirm that the new algorithm outperforms previous extended edge-finding algorithms, and sometimes results in better performance than standard edge-finding alone. Furthermore, we show that our method is competitive with the current state-of-the-art in edge-finding-based algorithms.

Keywords: constraint-based scheduling; global constraints; cumulative resources; task intervals; minimum slack; extended edge finding; filtering rules.

DOI: 10.1504/IJPS.2013.059678

International Journal of Planning and Scheduling, 2013 Vol.1 No.4, pp.264 - 284

Accepted: 04 Jun 2013
Published online: 30 Jun 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article