Horizontally Elastic Edge-Finder Algorithm for Cumulative Resource Constraint Revisited

Sévérine Fetgo Betmbe () and Clémentin Tayou Djamegni ()
Additional contact information
Sévérine Fetgo Betmbe: University of Dschang
Clémentin Tayou Djamegni: University of Dschang

SN Operations Research Forum, 2022, vol. 3, issue 4, 1-32

Abstract: Abstract The success of constraint programming on scheduling problems comes from the low complexity and power of propagators. The data structure Profile recently introduced by Gingras and Quimper in Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109, 2016, when applied to the edge-finder rule for the 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 in Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109, 2016 is revisited. It is proved that the data structure Profile can be further used for more adjustments. A new formulation of the horizontally elastic edge-finder rule is put forward. Similar to Gingras and Quimper in Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109, 2016, an $$\mathcal {O}(kn^2)$$ O ( k n 2 ) algorithm (where n is the number of tasks sharing the resource and $$k\le n$$ k ≤ n , the number of distinct capacities required by tasks) based on new attributes of the Profile data structure is proposed for the new rule. Experimental results on instances of Resource-Constrained Project Scheduling Problems (RCPSPs) from the benchmark suites highlight that using this new algorithm reduces the number of backtracks for the majority of instances with a slight increase in running time.

Keywords: Scheduling; Cumulative Constraint; Edge-Finder Rule; Profile; Constraint Programming; RCPSP (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-022-00172-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00172-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-022-00172-6

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().