noOverlap
OPL constraint (scheduling) used to prevent intervals in a sequence from overlapping and (optionally) to enforce a minimal distance between consecutive intervals.
| context | type |
|---|---|
| Model files (.mod) |
boolean (1 if the constraint is true, 0 otherwise) |
Syntax
noOverlap(p, M [,next]); //With a transition distance, matrix M
//between immediate successors (if next=true), or
//between all successors (if next=false)
Where:
p is a sequence variable
M is a distance matrix
next is a boolean
For example:
dvar sequence p in A [types T];
dvar interval A[];
int T[];
tuple triplet {int id1; int id2; int value;};
{triplet} M = ...;
A construction of noOverlap that shortcuts the creation of the interval sequence variable for simple cases where the sequence is not useful:
noOverlap(A); //Same as: dvar sequence p in A;
//noOverlap(p);
Description
The noOverlap constraint on an interval sequence variable p states that the sequence defines a chain of non-overlapping intervals, where 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 modelling disjunctive resources.
An optional transition matrix M (in the form of a non-negative integer tuple set) can be passed to the noOverlap constraint meaning that if ai appears before aj in the sequence, then a minimal distance M[typei,typej] must be respected between the end of ai and the start of aj (typei and typej denote the types of ai and aj in the sequence).
If a transition distance matrix M is specified, it defines the minimal non-negative distance that must separate 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 non-negative integer type of interval a in the
sequence variable p:
Note that if the transition matrix M satisfies the triangular inequality, the semantics of each of the two versions of the constraint noOverlap(π, M, Next) and noOverlap(π, M, After) is the same. If M does not satisfy the triangular inequality, constraint noOverlap(π, M, After) is stronger than noOverlap(π, M, Next).
Example
A set of n activities A[i] of integer type T[i] to be sequenced on a machine with a sequence dependent setup time abs(ti-tj) to switch from activity type ti to activity type tj with no activity overlap.
{int} Types = {T[i] | i in 1..n};
tuple triplet {int id1; int id2; int value;};
{triplet} M = {<i,j,ftoi(abs(i-j))> | i in Types, j in Types};
dvar interval A[i in 1..n] size d[i];
dvar sequence p in A types T;
subject to {
noOverlap(p, M);
};