Sequencing of interval variables

Describes a basic building block of scheduling, the interval sequence.

⊂π∀

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 k_A_underscore be a set of fixed intervals and n denote the cardinality of .

Note that the sequence alone does not enforce any constraint on the relative position of intervals 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 sequence variable also allows associating a fixed non-negative integer type with each interval variable in the sequence. In particular, these integers are used by the noOverlap constraint. T(p, a) denotes the fixed non-negative integer type of interval variable a in the sequence variable p.

Constraints on sequence variables

The following constraints are available on sequence variables:

first (scheduling)(p,a) states that if interval a is present, then it will be the first interval of the sequence p.
last (scheduling)(p,a) states that if interval a is present, then it will be the last interval of the sequence p.
before(p, a, b) states that if both intervals a and b are present then a will appear before b in the sequence p.
prev (scheduling)(p, a, b) states that if both intervals a and b are present then a will be just before b in the sequence p, that is, 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 is shown in the following table.

The no overlap constraint

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

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

If a transition distance matrix M is specified, it defines the minimal non-negative distance that must separate two consecutive intervals in the sequence.

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

A sequence variable together with a no-overlap constraint using it are illustrated in this figure:

The sameSequence and sameCommonSubsequence constraints

The sameSequence and sameCommonSubsequence constraints are binary constraints on a pair of sequence variables p₁ and p₂. 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 p₁ then the interval related to a is before the interval related to b in sequence p₂. Here are two examples of use-cases for these constraints.

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 classic 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(p₁, p₂, B₁, B₂) is defined on two sequence variables p₁ (defined on a set of interval variables A₁) and p₂ (defined on a set of interval variables A₂), with two arrays of interval variables B₁ and B₂ of identical size and such that B₁ ⊂ A₁, B₂ ⊂ A₂. The constraint states that the sub-sequences defined by p₁ and p₂ by only considering the pairs of present intervals (B₁[i], B₂[i]) are identical modulo the mapping between intervals B₁[i] and B₂[i].

For instance, let's suppose sequence variable p₁ defined on interval variables {a,b,c,d,e,f} and sequence variable p₂ defined on interval variables {u,v,w,x,y,z} with a constraint sameCommonSubsequence(p₁, p₂, [a,c,d,e,f], [u,w,v,x,y]). Assuming that, 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 considers only pairs of present intervals, the mapping B₁, B₂ maps [a,c,e] with [u,w,x]. Sub-sequence of π₁ over {a,c,e} is (c,a,e), sub-sequence of π₂ over {u,w,x} is (w,u,x) and one can see that the two sub-sequences are the same modulo the mapping.

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

∀i, j ∈ [1, n], i ≠ j, x(B₁[i]), x(B₁[j]), x(B₂[i]), x(B₂[j]), (π₁(B₁[i]) < π₁(B₁[j]) ⇔ π₂(B₂[i]) < π₂(B₂[j])

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

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

∀i ∈ [1, n], π₁(B₁[i]) = π₂(B₂[i])

When parameters B₁ and B₂ are omitted in the definition of the above constraints, we assume B₁ and B₂ are the definition intervals of p₁ and p₂, following the definition order of interval variables in the sequence.

Syntax and examples

For syntax and examples of use of the sequence interval variable, see sequence in the OPL Language Quick Reference.

For the syntax and examples of use of the no overlap constraint, which needs to be defined as a set of integer triples, see noOverlap in the OPL Language Quick Reference.

For the syntax and examples of the other constraints available on an interval sequence variable, see first, last (scheduling), prev (scheduling), before, sameSequence, and sameCommonSubsequence in the OPL Language Quick Reference. (Note that there are similarly-named constraints available for set operations in OPL.)

Note that none of the constraints mentioned in this section can be used in a meta-constraint.

Sequence variables can be viewed in a Gantt chart in the CPLEX® Studio IDE. A simple example is given in Viewing the results of scheduling problems.