An interval sequence variable is defined on a set of interval variables A. Informally speaking, the value of an interval sequence variable represents a total ordering of the interval variables of A. Note that any absent interval variables are not considered in the ordering.

More formally, an interval sequence variable  p on a set interval variables A represents a decision variable whose possible values are all the permutations of the intervals of A. Let be a set of fixed intervals and n denote the cardinality of . A permutation π of is a function π : { } [1, n] such that if we denote length(π) = |{, x()}| the number of present intervals:

Note that the sequence alone does not enforce any constraint on the relative position of interval end-points. For instance, an interval variable a could be sequenced before an interval variable b in a sequence p without any impact on the relative position between the start/end points of a and b (a could still be fixed to start after the end of b). This is because different semantics can be used to define how a sequence constrains the positions of intervals. We will see later how the noOverlap constraint implements one of these possible semantics.

The following constraints are available on sequence variables:

• first(p, a) states that if interval a is present, it will be the first interval of the sequence p.
• last(p, a) states that if interval a is present, it will be the last interval of the sequence p.
• before(p, a, b) states that if both intervals a and b are present, a will appear before b in the sequence p.
• prev(p, a, b) states that if both intervals a and b are present then a will be just before b in the sequence p. In other words, it will appear before b and no other interval will be sequenced between a and b in the sequence.

The formal semantics of these basic constraints are given in Table 3.

The sequence variable also allows the association of a fixed integer type with each interval variable in the sequence. In particular, these integers are used by the noOverlap constraint (see below) and the typeOfNext/Prev integer expressions (see below). T(p, a) denotes the fixed integer type of interval variable a in the sequence variable p.

The constraints involving interval variables and interval sequence variables cannot be used in logical constraints of CP Optimizer (see operator!, operator||). The reason is that any logical constraint involving interval variables must be captured via the presence Boolean value on the interval handled by the presenceOf constraint. The constraints having this limitation are the ordering constraints on a sequence (first, last, previous and before) and the noOverlap constraint.

The noOverlap constraint on an interval sequence variable p states that the sequence defines a chain of non-overlapping intervals, and any interval in the chain is constrained to end before the start of the next interval in the chain. This constraint is typically useful for modeling disjunctive resources.

More formally, the condition for a permutation value π for sequence p to satisfy the noOverlap constraint is defined as:

A sequence variable together with a no-overlap constraint using it are illustrated in Figure 4.

If a transition distance matrix M is specified, it defines the minimal distance that must separate two consecutive intervals in the sequence. Two versions of the constraint are available: one that enforces the transition distance between each interval and its next interval in the sequence (Next), and the other that enforces the transition distance between each interval and all its successors in the sequence (After).

More formally, if T(p,a) denotes the integer type of interval a in the sequence variable p:

Note that if the transition matrix M satisfies the triangular inequality, the semantics of the two versions of the constraint and are the same. If M does not satisfy the triangular inequality, constraint is stronger than .

The sameSequence and sameCommonSubsequence constraints are binary constraints on a pair of sequence variables and . These constraints state that the relative position of some related subsets of interval variables is the same in both sequences: typically, if a is before b in sequence then the interval related to a is before the interval related to b in sequence . Here are two examples of use-cases where these constraints are useful:

• First in/first out and no-bypass constraints. In some physical systems like trains on a single line railway or items on a conveyor belt, bypassing is not possible and items must enter and exit a given section of the system in the same order. If entering and exiting the sections or the junctions of the system is modeled by two related interval variables, those constraints can be modeled by sameSequence constraints (or sameCommonSubsequence constraints if the items do not follow the same path) on the sequences of entering and exiting intervals. A classical example of such a constraint is the permutation flow-shop scheduling problem.
• Scenario-Based approaches for scheduling with uncertainties. In presence of uncertainties (for instance, uncertain activity durations) one may be interested in building sequences of activities on unary resources that optimize some robustness or statistical criterion (for instance the expected makespan). A scenario is a sub-model that defines a particular realization of the uncertainties in the environment. As one must find robust sequences that optimize some criterion over all scenarios, the different sequences of a given unary resource across all scenarios are linked with sameSequence constraints.

A constraint sameCommonSubsequence() is defined on two sequence variables (defined on a set of interval variables ) and (defined on a set of interval variables ) with two arrays of interval variables and of identical size and such that . The constraint states that the sub-sequences defined by and by only considering the pairs of present intervals () are identical modulo the mapping between intervals and .

For instance, let's suppose sequence variable defined on interval variables {a,b,c,d,e,f} and sequence variable defined on interval variables {u,v,w,x,y,z} with a constraint sameCommonSubsequence(, ,[a,c,d,e,f],[u,w,v,x,y]). Assuming in a solution, interval variables d and y are absent while all the other interval variables are present. The pair of permutations =(c,f,a,e,b) and =(w,v,u,x) satisfies the sameCommonSubsequence constraints. Indeed if one only considers pairs of present intervals, the mapping maps [a,c,e] with [u,w,x]. Subsequence of over {a,c,e} is (c,a,e), subsequence of over {u,w,x} is (w,u,x) and one can see that the two subsequences are the same modulo the mapping.

More formally, let n denote the size of both interval variable arrays and . The condition for permutations and of sequencing variables and to satisfy constraint sameCommonSubsequence() is defined as:

A constraint sameSequence() is defined on two sequence variables of identical size (defined on a set of interval variables ) and (defined on a set of interval variables ) with two arrays of interval variables and that are an ordering of sets and . The constraint states that sequences and are identical modulo a mapping between intervals and . A sameSequence constraint is stronger than a sameCommonSubsequence constraint; it additionally imposes that arrays and contain all the definition intervals of their relative sequence variables and that the presence status of mapped interval variables and is the same.

More formally, let n denote the size of both sequence variables. The condition for permutations and of the sequence variables and to satisfy constraint sameSequence() is defined as:

when parameters and are omitted in the definition of the above constraints, we assume and are the definition intervals of and , following the order of definition of interval variables in the sequence.

Two integer expressions are available to get the type of the interval that is next (resp. previous) to a given interval variable a in a sequence p. When interval a is absent or is the last (resp. first) interval of the sequence, specific values can be provided for these integer expressions.

More formally, let π be the permutation value of a fixed sequence variable p, and be the value of a fixed interval variable a in the fixed sequence variable p.

If is present and is not the last interval in π, we denote the unique interval that is next to in π.

If is present and is not the first interval in π, we denote the unique interval that is previous to in π.

Integer expressions startOfNext, endOfNext, lengthOfNext, sizeOfNext, startOfPrev, endOfPrev, lengthOfPrev, and sizeOfPrev provide access to the different attributes of the interval that is next (resp. previous) to a given interval variable a in a sequence p. When interval a is absent or is the last (resp. first) interval of the sequence, specific values can be provided for these integer expressions.

The semantics of these expressions are given in the table below.