HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Horizontally Elastic Edge-Finder Algorithm for Cumulative Resource Constraint Revisited

Abstract : ABSTRACT. The success of the constraint programming on scheduling problems comes from the low complexity and power of propagators. The Profile data structure recently introduced by Gingras and Quimper in [1] when applied to the edge finder rule for cumulative resource constraint (which we call horizontally elastic edge finder) has improved the filtering power of this rule. In this paper, the algorithm proposed by Gingras and Quimper [1] is revisited. It is proved that the detection phase partially use the data structure Profile and a new formulation of the horizontally elastic edge finder rule is proposed. Similar to [1], a O(kn 2) algorithm (where k ≤ n represents the number of distinct capacities required by tasks and n the number of tasks sharing the resource) is proposed for the new rule. Experimental results on cumulative instances of resource constrained project scheduling problems (RCPSPs) from suites benchmarks highlight that using this new algorithm reduces the number of backtracks for a majority of instances with a marginal augmentation of the running time.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02931383
Contributor : Sévérine Fetgo Betmbe Connect in order to contact the contributor
Submitted on : Sunday, September 6, 2020 - 3:23:53 PM
Last modification on : Wednesday, October 7, 2020 - 12:14:27 PM
Long-term archiving on: : Wednesday, December 2, 2020 - 9:10:40 PM

File

CARI2020-10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02931383, version 1

Collections

Citation

Sévérine Fetgo Betmbe, Clémentin Djamegni. Horizontally Elastic Edge-Finder Algorithm for Cumulative Resource Constraint Revisited. CARI 2020, Oct 2020, THIES, Senegal. ⟨hal-02931383⟩

Share

Metrics

Record views

40

Files downloads

12