A quadratic extended edge-finding filtering algorithm for cumulative resource constraints. (1st January 2013)

• Record Type: Journal Article
• Authors: Kameugne, Roger; Fotso, Laure Pauline; Scott, Joseph
• Is Part Of: International journal of planning and scheduling. Volume 1:Number 4(2013)
• Page Start: 264
• Page End: 284
• Publication Date: 2013-01-01
• Subjects: constraint-based scheduling -- global constraint -- cumulative resource -- task intervals -- minimum slack -- edge-finding -- extended edge-finding; Production scheduling -- Periodicals; Mathematical statistics -- Periodicals; Operations research -- Periodicals; 658.53
• Languages: English
• ISSNs: 2044-494X

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 2 ) 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 2 ) (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.