State functions

Describes the state function.

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; yet 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 an activity that sets the oven temperature to a value v, and a cooking activity may follow that requires the oven temperature to start at and maintain a temperature level v' throughout its execution. Furthermore, the transition between two states is not always instantaneous and a transition time may be needed for the resource to switch from a state v to a state v'.

CP Optimizer introduces the notion of state function which is used to describe the evolution of a given feature of the environment. The possible evolution of this feature is constrained by interval variables of the problem. The main difference between state functions and cumulative 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. For instance for an oven with three 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, ...

Constraints are available to restrict the evolution of a state function. These constraints allow you to specify:

That the state of the function must be defined and should remain equal to a given non-negative state everywhere over a given fixed or variable interval (alwaysEqual).
That the state of the function must be defined and should remain constant (no matter its value) everywhere over a given fixed or variable interval (alwaysConstant).
That intervals requiring the state of the function to be defined cannot overlap a given fixed or variable interval (alwaysNoState).
That everywhere over a given fixed or variable interval, the state of the function, if defined, must remain within a given range of non-negative states [v_min, v_max] (alwaysIn).

Additionally, the two first 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 in the following figure where a₁ and a₂ are two start and end aligned interval variables, a₃ is start aligned only and a₄ is not aligned at all.

State functions and transition distance

A state function f is a decision variable whose value is a set of non-overlapping intervals, each interval [s_i, e_i) being associated a non-negative integer value v_i that represents the state of the function over the interval.

For instance, in the example of the oven introduced previously, we would have f_underscore (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, v'] 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 in the previous figure is consistent with the following transition distance:

Constraints on state functions

If f is a state function, a an interval variable, v, v_min, v_max non-negative integers and algn_s, algn_e two boolean values:

The constraint alwaysEqual(f, a, v, algn_s, algn_e) specifies that whenever a is present, state function f must be defined everywhere between the start and the end of interval a and be constant and equal to non-negative value v over this interval. If algn_s is true, it means that interval a is start-aligned with f: Interval a must start at the beginning of the interval where f is maintained in state s. If algn_e is true, it means that interval a is end-aligned with f: Interval a must end at the end of the interval where f is maintained in state s. More formally:
The constraint alwaysConstant(f, a, algn_s, algn_e) specifies that whenever a is present, state function f must be defined everywhere between the start and the end of interval a and be constant over this interval. More formally:
The constraint alwaysNoState(f, a) specifies that whenever a is present, state function f cannot provide any valid state between the start and the end of interval a. As a consequence, any interval constrained with alwaysEqual or alwaysConstant on this function and thus requiring the function to be defined cannot overlap interval a. Formally:
The constraint alwaysIn(f, a, v_min, v_max) specifies that whenever a is present, everywhere between the start and the end of interval a the state function f, if defined, must belong to the range [v_min, v_max] where 0 ≤ V_min ≤ V_max. Formally:

Syntax and examples

For the syntax and examples of use of a state function see stateFunction.

The results of a solved scheduling model can be viewed in the CPLEX Studio IDE. An example of results containing a state function is provided in Viewing the results of state functions in a Gantt chart.

Another example featuring a transition and the alwaysEqual constraint is shown in the following list.

The following list includes the constraints available on a state function. A full description and example for each syntax is available in the OPL Language Quick Reference.

alwaysEqual(f,s,e,v[,aligns,aligne]);
alwaysEqual(f,a,v[,aligns,aligne]);
alwaysConstant(f,s,e,[,aligns,aligne]);
alwaysConstant(f,a,[,aligns,aligne]);
alwaysNoState(f,s,e);
alwaysNoState(f,a);
alwaysIn(f,u,v,hmin,hmax);
alwaysIn(f,a,hmin,hmax);

Note that these constraints cannot be used in meta-constraints.

Example with stateFunction, transition, and alwaysEqual.

A machine can be equipped with a tool among a set of n possible tools. Each operation o executed on the machine needs a specific tool RequiredTool[o]. The machine can process several operation simultaneously provided these operations are compatible with the tool currently installed on the machine. Changing the tool installed on the machine needs some constant set-up time which is supposed to be independent from the tools.

int nbTools = ...;
int nbOps = ...;
int setupTime = ...;
range Tools = 1..nbTools;
range Operations = 1..nbOps;
int Duration [Operations] = ...;
int RequiredTool [Operations] = ...;

dvar interval op[o in Operations] size Duration[o];

tuple triplet { int tl1; int tl2; int value; };
{ triplet } Transition = { <tl1,tl2,setupTIme> } tl1, tl2 in Tools };
stateFunction machineTool with Transition;

constraints {
  forall(o in Operations) {
     alwaysEqual(machineTool, op[o], RequiredTool[o]);
  }
}