sameCommonSubsequence

Syntax

constraint sameCommonSubsequence(sequenceVar seq1, sequenceVar seq2)
constraint sameCommonSubsequence(sequenceVar seq1, sequenceVar seq2, intervalVarArray array1, intervalVarArray array2)

Parameters

• seq1: first constrained sequence variables.
• seq2: second constrained sequence variables.
• array1: first array of interval variables defining the mapping between the two sequence variables.
• array2: second array of interval variables defining the mapping between the two sequence variables.

Description

This function creates a same-common-subsequence constraint between sequence variables seq1 and seq2.

If no interval variable array is specified as argument, the sequence variables seq1 and seq2 should be of the same size and the mapping between interval variables of the two sequences is given by the order of the interval variables in the arrays array1 and array2 used in the definition of the sequences.

If interval variable arrays array1 and array2 are used, these arrays define the mapping between interval variables of the two sequences.

The constraint states that the sub-sequences defined by seq1 and seq2 by only considering the pairs of present intervals (array1[i], array2[i]) are identical modulo the mapping between intervals array1[i] and array2[i].

For more information on the sameCommonSubsequence constraint, see the concept Interval variable sequencing in CP Optimizer.

Example

The example below models a machine MA that produces some items that are then processed by two alternative machines MB1 and MB2. Once the items are produced they are dispatched and send to one of the machine MB1 or MB2 through specific conveyor belt. Items cannot bypass each other on the conveyor belts so if two items are sent to the same machine (MB1 or MB2), they must be processed on this machine in the same order as they were produced on machine MA.

a1 = intervalVar(size=5);
a2 = intervalVar(size=7);
a3 = intervalVar(size=6);
a4 = intervalVar(size=4);
b1  = intervalVar();
b11 = intervalVar(optional, size=11);
b12 = intervalVar(optional, size=15);
b2  = intervalVar();
b21 = intervalVar(optional, size=16);
b22 = intervalVar(optional, size=10);
b3  = intervalVar();
b31 = intervalVar(optional, size=15);
b32 = intervalVar(optional, size=9);
b4  = intervalVar();
b41 = intervalVar(optional, size=13);
b42 = intervalVar(optional, size=19);
MA  = sequenceVar([a1, a2, a3, a4]);
MB1 = sequenceVar([b11, b21, b31, b41]);
MB2 = sequenceVar([b12, b22, b32, b42]);
// Precedence constraints
endBeforeStart(a1, b1);
endBeforeStart(a2, b2);
endBeforeStart(a3, b3);
endBeforeStart(a4, b4);
// Machine selection
alternative(b1, [b11, b12]);
alternative(b2, [b21, b22]);
alternative(b3, [b31, b32]);
alternative(b4, [b41, b42]);
// Machine can process only one activity at a time
noOverlap(MA);
noOverlap(MB1);
noOverlap(MB2);
// No-bypass constraints
sameCommonSubsequence(MA, MB1);
sameCommonSubsequence(MA, MB2);
// Objective is to minimize the makespan
minimize(max([endOf(b1), endOf(b2), endOf(b3), endOf(b4)]));

An optimal solution to this problem with makespan 31 is the following schedule for the machines:

• Machine MA : a4 [0, 4) -> a2 [4, 11) -> a1 [11, 16) -> a3 [16, 22)
• Machine MB1: b41 [4, 17) -> b11 [17, 28)
• Machine MB2: b22 [11, 21) -> b32 [22, 31)

Requirements

• If no interval variable array is specified as an argument, the sequence variables seq1 and seq2 should be of the same size.
• If interval variable arrays array1 and array2 are used, those two arrays should be of the same size. Array array1 must only contain interval variables of sequence seq1 without any duplicate and array array2 must only contain interval variables of sequence seq2 without any duplicate. Note that in this case it is not required that the two sequences have the same size and the arrays can only contain a subset of the interval variables of their respective sequence variables.

Notes

There are two common use-cases of constraints sameCommonSubsequence and sameSequence:

• for modeling no-bypass constraints
• for building robust sequences of activities in stochastic scheduling problems by ensuring that, on a given machine, the same sequence of activity is used across different scenarios.