Overview | Group | Tree | Graph | Deprecated | Index | Concepts |
Semantics |
State functions and transition distance |
Constraints on state functions |
Some scheduling problems involve reasoning with resources whose state may change over time. The state of the resource can change because of the scheduled activities or because of exogenous events, and some activities in the schedule may need a particular condition on the resource state to be true in order to execute. For instance, the temperature of an oven may change due to the execution of an activity that sets the oven temperature to a value v and some cooking activity may require the oven temperature to be maintained at a temperature level v' during its execution. In some applications, the transition between two states is not instantaneous and a transition time is needed for the resource to switch from a state v to a state v'.
CP Optimizer introduces the notion of state function which is a function describing the evolution of a given feature of the environment. The possible evolution of this feature is constrained by the interval variables of the problem. The main difference between state functions and cumul functions (see section Cumul Functions) is that interval variables have an incremental effect on cumul functions (increasing or decreasing the function value) whereas they have an absolute effect on state functions (requiring the function value to be equal to a particular state or in a set of possible states).
Informally speaking, a state function is a set of non-overlapping intervals over which the function maintains a particular non-negative integer state. In between those intervals, the state of the function is not defined, typically because of an ongoing transition between two states (see State Functions and Transition Distance). For instance for an oven with 3 possible temperature levels identified by indexes 0, 1, and 2 we could have:
[start=0, end=100): state=0, [start=150, end=250): state=1, [start=250, end=300): state=1, [start=320, end=420): state=2, [start=460, end=560): state=0, ...
A set of constraints is available to restrict the evolution of a state function (see Constraints on State Functions). These constraints make it possible to specify:
Additionally, the alwaysEqual and alwaysConstant constraints can be complemented to specify that the given fixed or variable interval should have its start and/or end point synchronized with the start and/or end point of the interval of the state function that maintains the required state. This is the notion of start and end alignment which is particularly useful for modelling parallel batches. For instance in the oven example above, all interval variables that would require an oven temperature of level 1 and specify a start and end alignment, if executed over the interval [150, 250) would have to start exactly at 150 and end at 250. This is depicted on figure 6 where a1 and a2 are two start and end aligned interval variables, a3 is start aligned only and a4 is not aligned at all.
The constraints involving interval variables and a state function cannot be used in logical constraints of CP Optimizer (see operator!, operator||). The reason is that any logical constraint involving interval variables must be represented via the presence Boolean value on the interval handled by the presenceOf constraint. The constraints having this limitation are alwaysIn, alwaysNoState, alwaysConstant and alwaysEqual.
A state function f is a decision variable whose value is a set of non-overlapping intervals, each interval [si, ei) being associated a non-negative integer value vi that represents the state of the function over the interval.
For instance, in the example of the oven introduced above, we would have (200) = 1, s(, 200) = 150 and e(f, 200) = 250.
A state function can be associated with a transition distance. The transition distance defines the minimal distance that must separate two consecutive states in the state function.
More formally, if M[v, v0] represents a transition distance matrix between state v and state v', the transition distance means that:
The transition distance matrix M must satisfy the triangular inequality.
For instance, in the example of the oven, the state function depicted on Figure 6 is consistent with the following transition distance:
Notice that a transition distance between the same states can be nonzero, as it is for state 3 in this example.
If f is a state function, a an interval variable, v, vmin, vmax non-negative integers and two Boolean values:
In Figure 6, there are two adjacent intervals of state 1: the first one is [150,250) and the second one [250,300}. There are two reasons for that: 250 is end of end-aligned interval a1 and also start of start-aligned interval a2. Therefore due to condition (b) or (c) the interval [150,300) must be split in two (even though the state function does not change its value). Note also that thanks to condition (a) the interval a4 cannot overlap 250, despite the fact that a4 is neither start nor end aligned. To allow a4 to overlap 250, it would be necessary to use an alwaysIn constraint instead of alwaysEqual -- the difference is that alwaysIn does not enforce condition (a) even if the allowed state range is singleton (however, alwaysIn also allows the interval to overlap with state transitions).