stateFunction

OPL keyword (CP, scheduling) to create a state function.

Purpose

OPL keyword (CP, scheduling) to create a state function.

context
Model files (.mod)

Syntax

stateFunction f [with M];


With example optional argument M:

tuple triplet { int v1; int v2; int dist; };
{ triplet } M = ...;

Description

A state function is a function describing the evolution of a given feature of the environment. The possible evolution of this feature is constrained by interval variables of the problem. For example, a scheduling problem may contain a resource whose state changes over time. The resource state can change because of scheduled activities or because of exogenous events; some activities in the schedule may need a particular resource state in order to execute.

States of a state function are non-negative integers. The transition between two states is not always instantaneous, and a transition time may be necessary for the resource to switch states. Transitions are modeled with the optional argument M as a transition matrix that needs to be defined as a set of integer triplets (just as for the noOverlap constraint). Thus this matrix is a tuple set. Note that if there are two transition times in the matrix, the maximum will be considered. For example, <1,2,3>,<1,2,4> will be equivalent to <1,2,4>.

Note:

  1. By default, if a pair of states (i,j) is not referred to in the tuple set M representing the transition distance matrix, the default transition distance is 0, so stateFunction behaves as if the tuple <i,j,0> was in the set.

  2. The transition distance should satisfy triangular inequality.

  3. The possible states of the state function are between 0 and the maximal state referred to in the transition distance M.

Interval variables have an absolute effect on a state function, requiring the function value to be equal to a particular state or in a set of possible states.

If there is a duplicate in the transition matrix, such as:

<Index["m1"], Index["m2"], 70>
<Index["m1"], Index["m2"], 50>

the maximum value is used. So, in this example, 70 would be used.

Although stateFunction is a CP keyword it is still accepted as a CPLEX identifier. Note that the state function constraints alwaysIn, alwaysConstant, alwaysEqual, and alwaysNoState cannot be used in meta-constraints.

Example

A limited capacity oven is used to treat items in parallel batches. Items requiring incompatible temperatures cannot be treated in the same batch. Some setup time is needed to warm-up and cool-down the oven depending on the original and target temperature levels. The oven temperature is modelled as a state function. In a solution, the intervals of the state function represent the different batches. The treatment of each item is modelled by an interval variable. Because of parallel batching, items treated in the same batch need to be synchronized; they have the same start and end time, and this is modelled using the notion of start and end alignment.

Additionally a maintenance task is to be performed on the oven and during this maintenance task, the oven temperature should not reach high values (say, greater than level 4). This could be modelled by the additional constraint at the end.

int MaxItemsInOven = ...;
int NbItems = ...;
range Items = 1..NbItems;
int DurationMin[Items] = ...;
int DurationMax[Items] = ...;
int Temperature[Items] = ...;
tuple triplet { int t1; int t2; int value; };
{ triplet } Transition = ...;

dvar interval treat[i in Items] size DurationMin[i]..DurationMax[i];

stateFunction ovenTemperature with Transition;
cumulFunction itemsInOven = sum(i in Items) pulse(treat[i], 1);

constraints {
itemsInOven <= MaxItemsInOven;
forall(i in Items)

alwaysEqual(ovenTemperature, treat[i], Temperature[i], 1, 1);
}

dvar interval maintenance ...;

constraints {
// ...
alwaysIn(ovenTemperature, maintenance, 0, 4);
}