Skip to main content

Class: SequenceVar

Models a sequence (order) of interval variables.

Sequence variable is used together with noOverlap constraint that ensures that a set of interval variables do not overlap. Such no-overlapping set of interval variables will form a sequence in the solution. The sequence variable captures this order of interval variables and allows to express additional constraints on the order.

At the moment, sequence variable only allows to specify interval variable types for constraining transition distances between the intervals (see sequenceVar).

Hierarchy

Methods

getName

getName(): undefined | string

Returns the name assigned to the node.

Returns

undefined | string

Inherited from

ModelNode.getName


noOverlap

noOverlap(transitions?): void

Constrain the interval variables forming the sequence to not overlap.

Parameters

NameTypeDescription
transitions?number[][]2D square array of minimum transition distances the intervals. The first index is the type (index) of the first interval in the sequence, the second index is the type (index) of the second interval in the sequence.

Returns

void

Remarks

The noOverlap constraint make sure that the intervals in the sequence do not overlap. That is, for every pair of interval variables x and y at least one of the following conditions must hold (in a solution):

  1. Interval variable x is absent. This means that the interval is not present in the solution (not performed) and therefore it cannot overlap with any other interval. Only optional interval variables can be absent.
  2. Interval variable y is absent.
  3. x ends before y starts, i.e. x.end() is less or equal to y.start().
  4. y ends before x starts, i.e. y.end() is less or equal to x.start().

In addition, if transitions parameter is specified then the cases 3 and 4 are further constrained by the minimum transition distance between the intervals:

  1. x.end() + transitions[x.type][y.type] is less or equal to y.start().
  2. y.end() + transitions[y.type][x.type] is less or equal to x.start().

where x.type and y.type are the types of the interval variables x and y as given in Model.sequenceVar. If types were not specified then they are equal to the indices of the interval variables in the array passed to Model.sequenceVar. Transition times cannot be negative.

Note that transition times are enforced between every pair of interval variables, no only between direct neighbors.

The size of the 2D array transitions must be equal to the number of types of the interval variables.

This constraint is the same as Model.noOverlap(sequenceVar, ..). Constraint Model.noOverlap(intervalVarVar[], ..) is also the same but specifies the intervals directly instead of using a sequence variable.

Example

A worker must perform a set of tasks. Each task is characterized by:

  • length of the task (how long it takes to perform it),
  • location of the task (where it must be performed),
  • a time window startMin to endMax when the task must be performed.

There are three locations 0, 1 and 2, the minimum travel time between the locations is given by a transition matrix transitions. Transition times are not symmetric. For example, it takes 10 minutes to travel from location 0 to location 1 but 15 minutes to travel back from location 1 to location 0.

We are going to model this problem using noOverlap constraint with transition times.

// Travel times between locations:
let transitions = [
[ 0, 10, 10],
[15, 0, 10],
[ 5, 5, 0]
];
// Tasks to be scheduled:
const tasks = [
{location: 0, length: 20, startMin: 0, endMax: 100},
{location: 0, length: 40, startMin: 70, endMax: 200},
{location: 1, length: 10, startMin: 0, endMax: 200},
{location: 1, length: 30, startMin: 100, endMax: 200},
{location: 1, length: 10, startMin: 0, endMax: 150},
{location: 2, length: 15, startMin: 50, endMax: 250},
{location: 2, length: 10, startMin: 20, endMax: 60},
{location: 2, length: 20, startMin: 110, endMax: 250},
];

let model = new CP.Model;

// From the array tasks create an array of interval variables:
let taskVars = tasks.map((t, i) => model.intervalVar(
{ name: "Task" + i, length: t.length, start: [t.startMin,], end: [, t.endMax] }
));
// And an array of locations:
let types = tasks.map(t => t.location);

// Create the sequence variable for the tasks, location is the type:
let sequence = model.sequenceVar(taskVars, types);
// Tasks must not overlap and transitions must be respected:
sequence.noOverlap(transitions);

// Solve the model:
let result = await CP.solve(model, { solutionLimit: 1 });

setName

setName(name): SequenceVar

Assigns a name to the node.

Parameters

NameTypeDescription
namestringNamed to be assigned.

Returns

SequenceVar

The node itself so it can be used in chained expression.

Remarks

Assigning a name is optional. However is useful for debugging because variable names appear in the development traces. It is also useful for exporting the model to a file (see problem2json).

Example

let model = new CP.Model();
let x = model.intervalVar({ length: 10 }).setName("x");
// The line above is equivalent to:
// let x = model.intervalVar({ length: 10, name:"x" });
let endOfX = model.endOf(x).setName("endOfX");
let result = await CP.solve(model);

Inherited from

ModelNode.setName