2001 | OriginalPaper | Buchkapitel
Propagation of Cumulative Constraints
verfasst von : Philippe Baptiste, Claude Le Pape, Wim Nuijten
Erschienen in: Constraint-Based Scheduling
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Cumulative resource constraints represent the fact that activities A i use some amount cap(A i ) of resource throughout their execution. For a fully elastic activity A i , the cap(A i ) variable is not meaningful and we use a variable E(A i ) that represents the global “energy” required by the activity on the resource. Of course, for a non-elastic activity, we have E(A i ) = cap(A i )proc(A i ). In all case, enough resource must be allocated to activities, i.e., E(A i ) = Σ t E(A i , t), where E(A i , t) is the amount of resource used at t by A i . Recall that if A i is not an elastic activity, there are some strong relations between E(A i , t) and X(A i , t): E(A i , t) = X(A i , t)cap(A i ) For elastic activities, we have a weaker relation between the variables: [E(A i , t) # 0] ⇔ [X(A i i,t) # 0]. Generally speaking, the cumulative resource constraint can be stated as follows: $$ \forall t\sum\limits_i {E(A_i ,t)} \le cap $$ In the non-preemptive case, it can be rewritten as, $$ \forall t\sum\limits_{start(A_i ) \le t < end(A_i )} {cap(A_i )} \le cap $$ and in the preemptive case as, $$ \forall t\sum\limits_{start(A_i ) \le t < end(A_i )} {X(A_i ,t)cap(A_i )} \le cap $$ In the following, we note c i and e i the minimal amount of the capacity (resp. of the energy) of the resource required by A i . Finally we note C the maximum value in the domain of the resource capacity. In this chapter, we recall the most well-known techniques used to propagate the cumulative resource constraint. We focus on the fully elastic case in Section 3.1, on the preemptive case in Section 3.2 and, finally, on the non-preemptive case in Section 3.3.