License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.20
URN: urn:nbn:de:0030-drops-190574
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19057/
Go to the corresponding LIPIcs Volume Portal

Kameugne, Roger ; Betmbe, Sévérine Fetgo ; Noulamo, Thierry ; Djamegni, Clémentin Tayou

Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density

pdf-format:
LIPIcs-CP-2023-20.pdf (1 MB)

Abstract

In this paper, we propose an enhancement of the filtering power of the edge finding rule, based on the Profile and the TimeTable data structures. The minimal slack and the maximum density criteria are used to select potential task intervals for the edge finding rule. The strong detection rule of the horizontally elastic edge finder of Fetgo and Tayou is then applied on those intervals, which results in a new filtering rule, named Slack-Density Horizontally Elastic Edge Finder. The new rule subsumes the edge finding rule and it is not comparable to the Gingras and Quimper horizontally elastic edge finder rule and the TimeTable edge finder rule. A two-phase filtering algorithm of complexity ?(n²) (where n is the number of tasks sharing the resource) is proposed for the new rule. Improvements based on the TimeTable are obtained by considering fix part of external tasks which overlap with the potential task intervals. The detection and the adjustment of the improve algorithm are further increased, while the algorithm remains quadratic. Experimental results, on a well-known suite of benchmark instances of Resource-Constrained Project Scheduling Problems, show that the propounded algorithms are competitive with the state-of-the-art algorithms, in terms of running time and tree search reduction.

BibTeX - Entry

@InProceedings{kameugne_et_al:LIPIcs.CP.2023.20,
  author =	{Kameugne, Roger and Betmbe, S\'{e}v\'{e}rine Fetgo and Noulamo, Thierry and Djamegni, Cl\'{e}mentin Tayou},
  title =	{{Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19057},
  URN =		{urn:nbn:de:0030-drops-190574},
  doi =		{10.4230/LIPIcs.CP.2023.20},
  annote =	{Keywords: Horizontally Elastic Scheduling, Edge Finder Rule, Profile, TimeTable, Resource-Constrained Project Scheduling Problem}
}

Keywords: Horizontally Elastic Scheduling, Edge Finder Rule, Profile, TimeTable, Resource-Constrained Project Scheduling Problem
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI