Quadratic horizontally elastic not-first/not-last filtering algorithm for cumulative constraint

Roger Kameugne, Sévérine Fetgo Betmbe and Thierry Noulamo

European Journal of Operational Research, 2025, vol. 320, issue 3, 505-515

Abstract: The not-first/not-last rule is a pendant of the edge finding rule, generally embedded in the cumulative constraint during constraint-based scheduling. It is combined with other filtering rules for more pruning of the tree search. In this paper, the Profile data structure in which tasks are scheduled in a horizontally elastic way is used to strengthen the classic not-first/not-last rule. Potential not-first task intervals are selected using criteria (specified later in the paper), and the Profile data structure is applied to selected task intervals. We prove that this new rule subsumes the classic not-first rule. A quadratic filtering algorithm is proposed for the new rule, thus improving the complexity of the horizontally elastic not-first/not-last algorithm from O(n3) to O(n2). The fixed part of external tasks that overlap with the selected task intervals is considered during the computation of the earliest completion time of task intervals. This improvement increases the filtering power of the algorithm while remaining quadratic. Experimental results, on a well-known suite of benchmark instances of Resource-Constrained Project Scheduling Problems (RCPSPs), show that the propounded algorithms are competitive with the state-of-the-art not-first algorithms in terms of tree search and running time reduction.

Keywords: Not-first/not-last algorithm; Profile data structure; TimeTable data structure; Cumulative scheduling; Constraint programming; Horizontally elastic scheduling; RCPSP (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724006945
Full text for ScienceDirect subscribers only

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:eee:ejores:v:320:y:2025:i:3:p:505-515

DOI: 10.1016/j.ejor.2024.09.003

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().