A cumulative not-first/not-last filtering algorithm in O(n 2log(n))

Roger Kameugne () and Laure Pauline Fotso ()
Additional contact information
Roger Kameugne: University of Maroua
Laure Pauline Fotso: University of Yaoundé I

Indian Journal of Pure and Applied Mathematics, 2013, vol. 44, issue 1, 95-115

Abstract: Abstract In cumulative and disjunctive constraint-based scheduling, the resource constraint is enforced by several filtering rules. Among these rules, we have (extended) edge-finding and not-first/not-last rules. The not-first/not-last rule detects tasks that cannot run first/last relatively to a set of tasks and prunes their time bounds. In this paper, it is presented a sound O (n 2 log n) algorithm for the cumulative not-first/not-last rule where n is the number of tasks. This algorithm reaches the same fix point as previous not-first/not-last algorithms, although it may take additional iterations to do so. The worst case complexity of this new algorithm for the maximal adjustment is the same as our previous complete O (n 2|H| log n) not-first/not-last algorithm [7] where |H| is the maximum between the number of distinct earliest completion and latest start times of tasks. But, experimental results on benchmarks from the Project Scheduling Problem Library (PSPLib) and the Baptiste and Le Pape data set (BL) suggest that the new not-first/not-last algorithm has a substantially reduced runtime. Furthermore, the results demonstrate that in practice the new algorithm rarely requires more propagations than previous not-first/not-last algorithms.

Keywords: Constraint-based scheduling; global constraints; not-first/not-last; cumulative resources; cumulative Θ-tree; energy envelope (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s13226-013-0005-z 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:indpam:v:44:y:2013:i:1:d:10.1007_s13226-013-0005-z

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

DOI: 10.1007/s13226-013-0005-z

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().