3.7.188. Phi-tree

A constraint for which one of its filtering algorithms uses a balanced binary tree in order to efficiently evaluate the maximum or minimum value of a formula over all possible subsets of tasks Ξ© of a given set of tasks Ξ¦. Ξ¦-trees were introduced by P.Β VilΓ­m, first in the context of unary resources inΒ [Vilim04] and inΒ [Vilim07], and later on in the context of cumulative resourcesΒ [Vilim09a], [Vilim09b]. Without loss of generality, let us sketch the main idea behind a Ξ¦-tree in the context of a cumulative resource of capacity C. For this purpose we follow the description given inΒ [Vilim09a]. Given a set of tasks Ξ¦ where each task has an earliest possible start, a latest possible end, a duration and a resource consumption, assume we need to evaluate the earliest completion time over all tasks of Ξ¦ under the hypothesis that we should not exceed the maximum resource capacity C. Let us first introduce some notations:

  • Ξ© denotes any non-empty subset of tasks of Ξ¦.

  • 𝑒𝑠𝑑 Ξ© is the minimum over the earliest starts of the tasks in Ξ©.

  • e Ξ© is the sum of the surfaces (i.e., the product of the duration by the resource consumption) of the tasks in Ξ©.

Figure 3.7.51. Example of Ξ¦-tree associated with four tasks of respective duration and resource consumption 3Γ—4, 1Γ—3, 5Γ—5, 2Γ—4 and of respective earliest start 1, 3, 8, 9 under the assumption that the maximum capacity of the cumulative resource is equal to 5

A common estimation of the earliest completion time over all tasks of Ξ¦ is max Ξ©βŠ†Ξ¦ 𝑒𝑠𝑑 Ξ© +e Ξ© C which can be rewritten as max Ξ©βŠ†Ξ¦ C𝑒𝑠𝑑 Ξ© +e Ξ© C. The numerator of the last fraction is called the energy envelope of the set of tasks Ξ¦ and the purpose of a Ξ¦-tree is to evaluate this quantity efficiently. For a node n, let β„’(n) denote the set of leaves of the sub-tree rooted at n. The leaves of the Ξ¦-tree correspond to the tasks of Ξ¦ sorted from left to right by increasing earliest start. Each node n of the Ξ¦-tree records both, the sum of the surfaces of the tasks in β„’(n), as well as the energy envelope of the tasks in β„’(n). The sum of the surfaces associated with a non-leave node n of the tree corresponds to the sum of the surfaces of the children of n, while the energy envelope of n is equal to the maximum between on the one hand, the energy envelop of its right child and on the other hand the sum of the energy envelop of its left child and the recorded sum of surfaces of its right child (seeΒ [Vilim09a] for a justification of these recursive formulae). FigureΒ 3.7.51 illustrates the construction of a Ξ¦-tree associated with four given tasks.