C++ Reference: class TimeTableEdgeFinding
This documentation is automatically generated.TimeTableEdgeFinding implements the timetable edge finding filtering rule presented in Vilim Petr, "Timetable edge finding filtering algorithm for discrete cumulative resources", CPAIOR 2011, http://vilim.eu/petr/cpaior2011.pdf.
This propagator runs in O(n^2) where n is the number of tasks. It increases both the start times and decreases the ending times of the tasks.
Note that this propagator does not ensure that the cumulative constraint holds. It should thus always be used with at least a timetable propagator.
The algorithm relies on free tasks. A free task is basically a task without its mandatory part. For instance:
s_min s_max e_min e_max v v v v task: ============================= ^ ^ ^ | free part | Mandatory part |
Obviously, the free part of a task that has no mandatory part is equal to the task itself. Also, a free part cannot have a mandatory part by definition. A fixed task thus have no free part.
The idea of the algorithm is to use free and mandatory parts separately to have a better estimation of the energy contained in a task interval.
If the sum of the energy of all the free parts and mandatory subparts contained in a task interval exceeds the amount of energy available, then the problem is unfeasible. A task thus cannot be scheduled at its minimum start time if this would cause an overload in one of the task intervals.