sameSequence
A binary constraint on a pair of sequence variables. The constraint states that the relative position of related interval variables is the same in both sequences, seq1 and seq2.
| context | type |
|---|---|
| Model files (.mod) - Not allowed in a CPLEX constraint block. | Boolean (1 if the constraint is true, 0 otherwise) |
Syntax
dvar sequence seq1 in ...;
dvar sequence seq2 in ...;
dvar interval a1[...] ...; // Reordering of the interval variables of seq1
dvar interval a2[...] ...; // Reordering of the interval variables of seq2
constraints {
sameSequence(seq1, seq2, a1, a2); // relates a1[i] to a2[i]
sameSequence(seq1, seq2); // intervals are related according to their order in the definition of the sequences
}Description
This function creates a same-sequence constraint between sequence variables seq1 and seq2. Sequence variables seq1 and seq2 should be of the same size. The mapping between interval variables of the two sequences is specified by arrays a1 and a2. Arrays a1 and a2 should be of the same size. The constraint states that the two sequences seq1 and seq2 are identical modulo a mapping between intervals a1[i] and a2[i]. By default, the name of the constraint is the empty string, but you can specify a name of your own choice.sameSequence is a stronger constraint than sameCommonSubsequence.
Examples
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 a criterion over all scenarios, the different sequences of a given unary resource across all scenarios are linked with sameSequence constraints.
Provided in the distribution is an example that illustrates the use of same-sequence constraints for modeling the permutation flow-shop scheduling problem.
The following examples are provided in the distribution to illustrate the use of sameSequence constraints for modeling scheduling problems.
<Install_dir>/opl/examples/opl/sched_pflowshop/sched_pflowshop.mod
<Install_dir>/opl/examples/opl/sched_stochastic_jobshop/sched_stochastic_jobshop.mod