Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources

Autor:	Petr Vilím
Rok vydání:	2011
Předmět:	Mathematical optimization Computation Constraint programming New variant Fixed point Data structure Algorithm Upper and lower bounds Time complexity Mathematics Scheduling (computing)
Zdroj:	Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ISBN: 9783642213106 CPAIOR
DOI:	10.1007/978-3-642-21311-3_22
Popis:	Edge Finding filtering algorithm is one of the reasons why Constraint Programming is a successful approach in the scheduling domain. However edge finding for cumulative resources was never as successful as edge finding for disjunctive resources. This paper presents a new variant of the edge finding algorithm which improves filtering by taking into account minimum capacity profile - a data structure known from timetabling algorithm. In comparison with standard and extended edge finding algorithms the new algorithm is stronger but it may need more iterations in order to reach the fixpoint. Time complexity of the algorithm is O(n2) where n is number of activities on the resource. We also propose further improvement of the filtering by incorporating some ideas from not-first/not-last and energetic reasoning algorithms. The filtering power of the algorithm is tested on computation of destructive lower bounds for 438 open RCPSP problems. For 169 of them we improve current best lower bound, in 9 cases backtrack free.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::312a446bea49746fb71ac990d8145a64 https://doi.org/10.1007/978-3-642-21311-3_22 Zobrazit plný text záznamu