Max Energy Filtering Algorithm for Discrete Cumulative Resources

Autor:	Petr Vilím
Rok vydání:	2009
Předmět:	Mathematical optimization Computer science Constraint programming Start time Algorithm Time complexity Scheduling (computing)
Zdroj:	Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ISBN: 9783642019289 CPAIOR
DOI:	10.1007/978-3-642-01929-6_22
Popis:	In scheduling using constraint programming we usually reason only about possible start times and end times of activities and remove those which are recognized as unfeasible. However often in practice there are more variables in play: variable durations of activities and variable resource capacity requirements. This paper presents a new algorithm for filtering maximum durations and maximum capacity requirements for discrete cumulative resources. It is also able to handle optional interval variables introduced in IBM ILOG CP Optimizer 2.0. Time complexity of the algorithm is ${\mathcal O}(n {\rm log} n)$. The algorithm is based on never published algorithm by Wim Nuijten and a on slightly modified e-feasibility checking algorithm by Armin Wolf and Gunnar Schrader. The later algorithm is also described in the paper.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b070b5d09d0151371588884dc4b00af4 https://doi.org/10.1007/978-3-642-01929-6_22 Zobrazit plný text záznamu