 |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
The Theta-Lambda tree can be used to implement several scheduling algorithms.
This template class is instantiated only for IntegerValue and int64_t.
The tree structure itself is a binary tree coded in a vector, where node 0 is unused, node 1 is the root, node 2 is the left child of the root, node 3 its right child, etc.
The API gives access to rightmost events that realize a given envelope.
See: _ (0) Petr Vilim's PhD thesis "Global Constraints in Scheduling". _ (1) Petr Vilim "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)" _ (2) Petr Vilim "Max energy filtering algorithm for discrete cumulative resources". _ (3) Wolf & Schrader "O(n log n) Overload Checking for the Cumulative Constraint and Its Application". _ (4) Kameugne & Fotso "A cumulative not-first/not-last filtering algorithm in O(n^2 log n)". _ (5) Ouellet & Quimper "Time-table extended-edge-finding for the cumulative constraint".
Instead of providing one declination of the theta-tree per possible filtering algorithm, this generalization intends to provide a data structure that can fit several algorithms. This tree is based around the notion of events. It has events at its leaves that can be present or absent, and present events come with an initial_envelope, a minimal and a maximal energy. All nodes maintain values on the set of present events under them: _ sum_energy_min(node) = sum_{leaf \in leaves(node)} energy_min(leaf) _ envelope(node) = max_{leaf \in leaves(node)} initial_envelope(leaf) + sum_{leaf' \in leaves(node), leaf' >= leaf} energy_min(leaf').
Thus, the envelope of a leaf representing an event, when present, is initial_envelope(event) + sum_energy_min(event).
We also maintain envelope_opt with is the maximum envelope a node could take if at most one of the events were at its maximum energy. _ energy_delta(leaf) = energy_max(leaf) - energy_min(leaf) _ max_energy_delta(node) = max_{leaf \in leaves(node)} energy_delta(leaf) _ envelope_opt(node) = max_{leaf \in leaves(node)} initial_envelope(leaf) + sum_{leaf' \in leaves(node), leaf' >= leaf} energy_min(leaf') + max_{leaf' \in leaves(node), leaf' >= leaf} energy_delta(leaf');
Most articles using theta-tree variants hack Vilim's original theta tree for the disjunctive resource constraint by manipulating envelope and energy: _ in (0), initial_envelope = start_min, energy = duration _ in (3), initial_envelope = C * start_min, energy = demand * duration _ in (5), there are several trees in parallel: initial_envelope = C * start_min or (C - h) * start_min energy = demand * duration, h * (Horizon - start_min), or h * (end_min). _ in (2), same as (3), but putting the max energy instead of min in lambda. _ in OscaR's TimeTableOverloadChecker, initial_envelope = C * start_min - energy of mandatory profile before start_min, energy = demand * duration
There is hope to unify the variants of these algorithms by abstracting the tasks away to reason only on events.
Definition at line 93 of file scheduling.h.
#include <scheduling.h>
Public Member Functions | |
| ThetaLambdaTree ()=default | |
| Builds a reusable tree. Initialization is done with Reset(). | |
| void | Reset (int num_events) |
| void | AddOrUpdateEvent (int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max) |
| void | AddOrUpdateOptionalEvent (int event, IntegerType initial_envelope_opt, IntegerType energy_max) |
| void | RemoveEvent (int event) |
| Makes event absent, compute the new envelope in O(log n). | |
| IntegerType | GetEnvelope () const |
| IntegerType | GetOptionalEnvelope () const |
| int | GetMaxEventWithEnvelopeGreaterThan (IntegerType target_envelope) const |
| IntegerType | GetEnvelopeOf (int event) const |
| void | GetEventsWithOptionalEnvelopeGreaterThan (IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const |
| IntegerType | EnergyMin (int event) const |
| Getters. | |
|
default |
Builds a reusable tree. Initialization is done with Reset().
|
inline |
Makes event present and updates its initial envelope and min/max energies. This updates the tree in O(log n).
Definition at line 106 of file scheduling.h.
|
inline |
Adds event to the lambda part of the tree only. This will leave GetEnvelope() unchanged, only GetOptionalEnvelope() can be affected, by setting envelope to std::numeric_limits<>::min(), energy_min to 0, and initial_envelope_opt and energy_max to the parameters. This updates the tree in O(log n).
Definition at line 123 of file scheduling.h.
|
inline |
Getters.
Definition at line 198 of file scheduling.h.
|
inline |
Returns the maximum envelope using all the energy_min in O(1). If theta is empty, returns std::numeric_limits<>::min().
Definition at line 146 of file scheduling.h.
| IntegerType operations_research::ThetaLambdaTree< IntegerType >::GetEnvelopeOf | ( | int | event | ) | const |
Returns initial_envelope(event) + sum_{event' >= event} energy_min(event'), in time O(log n).
Definition at line 293 of file scheduling.h.
|
inline |
Computes a pair of events (critical_event, optional_event) such that if optional_event was at its maximum energy, the envelope of critical_event would be greater than target_envelope.
This assumes that such a pair exists, i.e. GetOptionalEnvelope() should be greater than target_envelope. More formally, this finds events such that: initial_envelope(critical_event) + sum_{event' >= critical_event} energy_min(event') + max_{optional_event >= critical_event} energy_delta(optional_event) > target envelope.
For efficiency reasons, this also fills available_energy with the maximum energy the optional task can take such that the optional envelope of the pair would be target_envelope, i.e. target_envelope - GetEnvelopeOf(event) + energy_min(optional_event).
This operation is O(log n).
Definition at line 186 of file scheduling.h.
|
inline |
Computes the maximum event s.t. GetEnvelopeOf(event) > envelope_max. There must be such an event, i.e. GetEnvelope() > envelope_max. This finds the maximum event e such that initial_envelope(e) + sum_{e' >= e} energy_min(e') > target_envelope. This operation is O(log n).
Definition at line 158 of file scheduling.h.
|
inline |
Returns the maximum envelope using the energy min of all task but one and the energy max of the last one in O(1). If theta and lambda are empty, returns std::numeric_limits<>::min().
Definition at line 151 of file scheduling.h.
|
inline |
Makes event absent, compute the new envelope in O(log n).
Definition at line 135 of file scheduling.h.
| void operations_research::ThetaLambdaTree< IntegerType >::Reset | ( | int | num_events | ) |
Initializes this class for events in [0, num_events) and makes all of them absent. Instead of allocating and de-allocating trees at every usage, i.e. at every Propagate() of the scheduling algorithms that uses it, this class allows to keep the same memory for each call.
Because the algorithm needs to access a node sibling (i.e. node_index ^ 1), our tree will always have an even number of leaves, just large enough to fit our number of events. And at least 2 for the empty tree case.
If num_leaves is not a power or two, the last depth of the tree will not be full, and the array will look like: [( num_leafs parents)(leaves at depth d - 1)(leaves at depth d) The first leaves at depth p will have power_of_two_ as index.
Definition at line 270 of file scheduling.h.
1.14.0