Basic concepts

Intervals

Interval variables (or just intervals) are the main decision variable in scheduling. They represent a task to be performed.

OptalCP decides the start and length of all interval variables, based on the parameters provided by the user

• bounds : min / max start time, min / max end time, min / max length
• constraints to be satisfied
• objective function

Here is an example with

• start in [0 .. 50]
• end in [100 .. 250]
• length in [25 .. 175]

Because of the equation $length = end - start$ only two out of the three variables need to be fixed.

FIXME : SVG scale and html scale differ: labels move when zoom in/out in browser

start

end

Decision variables

Different optimization engines may manipulate different types of variables (and different types of constraints). In general one can expect that

• SAT engines use boolean variables
• SMT engines use the type of variables that are available in the theories they implement. Typical theories are bit-vectors, arrays, rationals and integers
• CP based scheduling engines use interval variables and integer variables
• MIP engines use floating point and integer variables
• LS engines use floating point and integer variables

Propagation

While playing with the widget, you may have noticed that not all start times, end times or lengths can be achieved.

• The minimum length is 50 (with start = 50 and end = 100)
• The maximum end time is 225 (with start = 50 and length = 175)

Constraint propagation is the reduction of the variable bounds (or domains) based on deductions that can be made from the problem constraints. Here the only constraint is the implicit constraint start + end = length.

After propagation the task becomes

The engine will propagate all constraints till fix point that is until it is not able to make any further reduction.

Deductions

There are may forms of deductions. The terms domain reduction and bound propagation are synonyms. Terms like cut generation, conflict generation or symmetry breaking all refer to some more advanced types of deductions that can also result directly or indirectly in a reductio nof the variable domains

Precedences

A precedence is an inequality between the start end end times of two interval variables

Consider the following pseudo-code in OPtaL (a language similar to OPL)

dvar interval A in 0 .. 10 length 5 .. 10
dvar interval B in 0 .. 20 length 5 .. 10

constraints {
    end A <= start B
}

The code requests the creation of

• an interval A with start in [0 .. 10], end in [0 .. 10] and length in [5..10]
• an interval B with start in [0 .. 20], end in [0 .. 20] and length in [5..10]
• a constraint end A <= start B

It is common that a global domain is given for both start and end variables rather than individual domains for each one. That means the task needs to fit in the range 0 .. 10.

The engine will adjust the individual bounds as follows

• start A in [0 .. 10] and length A in [5 .. 10] => end A in [5 .. 10]
• end A in [5 .. 10] and length A in [5 .. 10] => start A in [0 .. 5]
• end A in [5 .. 10] and end A <= start B => start B in [5 .. 20]
• start B in [5 .. 20] and length B in [5 .. 10] => start B in [5 .. 15]
• start B in [5 .. 15] and length B in [5 .. 10] => end B in [10 .. 20]

Precedences may contain constants start A <= start B + 10 or even arbitrary arithmetic operations start A <= 2 * (start B) + 3 * (length B) or logic operators end A <= start B || end B <= start A.

Search

You may also have noticed that even after propagation, there is not enough information to fix the variables : a large variety of start times and lengths are still possible.

Engines decide appropriate values for the variables (here start time and length). They will consider many combinations of values and retain the best one they have found. In this context the best is the one that has the best objective value (which we explain below)

Everything else being equal, OptalCP with always choose the smallest starting time and length possible. That's the leftmost schedule

Yes

No

No

Search strategies

The common types of search strategies are tree search and local search. OptalCP just like most engines uses a combination of local and tree search:

• Large Neighborhood Search (LNS) [Shaw 1997] is a local search technique that uses a tree search as a subroutine to search neighborhoods
• Failure Directed Search (FDS) [Vilim 2015] is a nogood-directed tree search useful for proving optimality

Objectives

An objective is a function that the engine has to maximize or minimize.

Common objectives include

• makespan is the maximum of the completion time of tasks
• tardiness is the sum of the difference between the time a task was completed and its due date
• lateness is the sum of the delays between a task completion and its due date

Makespan

The makespan is the time of completion of the last task

$\max_k \mathrm{end}\ T_k$

Lateness

When tasks have an ideal completion time, the lateness measures the distance between the ideal completion of each task and its real completion time

$\sum_k (\mathrm{end}\ T_k - \mathrm{due}_k)$

The due dates can be grouped into a constant and only the sum of end times remains

$C + \sum_k \mathrm{end}\ T_k$

Very often we just ignore the constant term $C$ and call lateness the sum of end times.

Tardiness

Tasks have a due date but no penalty is incurred unless the task is completed after the due date.

$\sum_k \max(0, \mathrm{end}\ T_k - \mathrm{due}_k)$

Multi-objective optimization

OptalCP doesn't support yet multiple objectives. Lexicographic objectives can be simulated for now as a weighted sum.

APIs

As of today the main way of using the engine is via TypeScript or JavaScript on top of NodeJS.

A typical JavaScript / Typescript model has the following structure

import * as CP from '@optal/cp' // include the lib

const model = new CP.Model // create an empty model

const x = <IntervalVar> Array (10) // create decision variables

for (let i = 0; i < 10; i++) 
    x[i] = model.intervalVar({ length: 2, name: `x${i}` })

model.minimize(model.max(x)) // define objective

for (let i = 1; i < 10; i++) x[i-1].endBeforeStart(x[i]) // add constraints

CP.solve(model) // solve

We also provide all models in a pseudo-code we call OPtaL for convenience, as OPtaL models tend to be significantly shorter than their TypeScript / JavaScript counterpart.

dvar interval x [1 .. 10] length 2 // create and initialize decision variables

minimize max (i in 1 .. 10) end x[i] // define objective

constraints {

    forall (i in 2 .. 10) end x[i - 1] <= start x[i] // add constraints

}

tip

In programmatic APIs like JavaScript the order of the model declarations is rather free. For instance instead of declaring all the variables at one point, then initializing them all and later adding all the constraints, you could do multiple small blocks with declaration-initialization-constraints. But we strongly recommend to stick to a style that is close to OPtaL pseudocode and the examples provided, as it is very easy to get lost and confused in a large JavaScript model otherwise.

Project Scheduling Problem (PSP)

The project scheduling problem (PSP) consists in scheduling all tasks needed to complete a project in the minimum time possible.

There are many variants that model different ways to allocate the resources needed to perform said tasks. We will consider here the simplest version that only involves tasks and precedences.

Construction of the Millau Viaduct

Image: Foster and partners

The construction of the Millau viaduct required

• Erecting 7 piers
• Building 2 abutments, one on each side
• Setting up a construction site on each abutment to manufacture the steel decks
• Manufacturing the decks (transportation of parts, assembly, welding)
• Moving the decks into place using temporary intermediate piers for support
• Joining the decks in the middle
• Installing the pylons and attaching the stays

Image: Foster and partners

Modeling

Every optimization problem requires a **modeling phase ** where assumptions and simplifications are made in order to map the reality into decision variables and constraints.

For instance we could choose to

• merge the construction of the abutments and deck manufacturing sites into a single interval, or keep them separate
• ignore the transportation of the parts and only create an interval for the manufacturing of the decks
• cut the deck manufacturing into independently managed sections, each one having its corresponding interval, or treat the whole manufacturing as a single interval

All these modeling decisions are equally valid and represent different levels of granularity of the problem. Depending on the customer, the data, the constraints needed and performance expectations, a higher or lower level of granularity may be required.

Modeling is crucial

Modeling is a crucial step in solving real life optimization problems. Most of the time problems seen in optimization manuals have been stripped of this phase and are presented in a way where there is a single obvious model. This makes the exercise simpler to handle (only one "solution"), but hides a very important aspect of the work.

Diving straight into coding without considering different ways of mapping the problem into scheduling concepts will inevitably lead to problems (poor performance, excessively complex models, inability to add some constraints)

A model only with precedences

In this model we ignore all resources and just focus on scheduling the large tasks to have an idea of the order in which they should be done, and the total completion time for the project. We also solve the problem as if the construction was proceeding from left to right (in reality the bridge is built from both sides at the same time)

The core of the problem is the precedence relationship between the deck sections and the piers.

We introduce intervals for the piers, the temporary piers and the deck sections with the following precedences

dvar interval pier [0 .. n - 1] length build_pier
dvar interval temp_pier [0 .. n - 1] length build_temp_pier
dvar interval deck [0 .. n - 1] length position_deck

forall (i in 0 .. n - 1) {
    if (i > 0) start deck[i] >= end deck [i - 1] 
    start deck[i] >= end pier[i]
    start deck[i] >= end temp_pier[i]
    if (i > 0) start deck[i] >= end pier[i - 1] // pier[-1] is the abutment
}

Now we want to model the fact that temporary piers are a unique resource, that is they need to be disassembled in position n before being remounted in position n + 1. To do so, we will introduce a new interval disassemble_temp_pier[1..n] and constrain the disassembling operations to be interleaved with the mounting operations.

We also can only disassemble the temp_pier[i] once the deck[i] is installed

dvar interval disassemble_temp_pier [0 .. n - 1] length unbuild_temp_pier

forall (i in 0 .. n - 1) {
    end temp_pier[i] <= start disassemble_temp_pier[i]
    end desk[i] <= start disassemble_temp_pier[i]
    if (i > 0) end disassemble_temp_pier[i - 1] <= start temp_pier[i]
}   

Finally we add an activity for the abutment and setting up of the construction site, and another one for the deck junction (last deck), installing the pylons and attaching the stays

dvar interval abutment length setup_abutment
dvar interval everything_else length others

forall (i in 0 .. n - 1) end abutment <= start deck[i]
forall (i in 0 .. n - 1) end deck[i] <= start everything_else

We can now assemble everything into a single model and add a makespan objective and translate into JavaScript / TypeScript

OPtaL

int build_pier = 10
int build_temp_pier = 4
int unbuild_temp_pier = 2
int position_deck = 4
int setup_abutment = 2
int others = 10

int n = 7

range phases = 1 .. n

dvar interval pier [phases] length build_pier
dvar interval temp_pier [phases] length build_temp_pier
dvar interval disassemble_temp_pier [phases] length unbuild_temp_pier
dvar interval deck [phases] length position_deck
dvar interval abutment length setup_abutment
dvar interval everything_else length others

minimize end everything_else

constraints {

    // Deck is built on top of piers and after previous deck
    forall (i in phases) {
        start deck[i] >= end pier[i]
        start deck[i] >= end temp_pier[i]
    }

    forall (i in phases : i - 1 in phases) {
        start deck[i] >= end deck [i - 1] 
        start deck[i] >= end pier[i - 1]
    }

    // Temporary pier is a unique resource
    forall (i in phases) {
        end temp_pier[i] <= start disassemble_temp_pier[i]
        end deck[i] <= start disassemble_temp_pier[i]
    }

    forall (i in phases : i - 1 in phases)
        end disassemble_temp_pier[i - 1] <= start temp_pier[i] 

    // Setup abutment and construction side before decks are built
    forall (i in phases) end abutment <= start deck[i]

    // Pylons and stays
    forall (i in phases) end deck[i] <= start everything_else
}

TypeScript

tip

Explicitly marking sections in the source code (Data, Model, variables, Objective, Constraints, Solve) may seem overkill for small pieces of code but will allow you to quickly understand what you are looking at in larger models. Hence we recommend getting used to adding them

import * as CP from '@optal/cp'

//////////
// Data //
//////////

// Parameters

const build_pier = 10
const build_temp_pier = 4
const unbuild_temp_pier = 2
const position_deck = 4
const setup_abutment = 2
const others = 10

const n = 7

///////////
// Model //
///////////

const model = new CP.Model

////////////////////////
// Decision variables //
////////////////////////

const pier = <IntervalVar> Array (n)
const temp_pier = <IntervalVar> Array (n)
const disassemble_temp_pier = <IntervalVar> Array (n)
const deck = <IntervalVar> Array (n)
const abutment = IntervalVar ({ length: setup_abutment })
const everything_else = IntervalVar ({ length: others })

// Initializations

for (let i = 0; i < n; i++) {
    pier[n] = IntervalVar({ length: build_pier })
    temp_pier[n] = IntervalVar({ length: build_temp_pier })
    disassemble_temp_pier[n] = IntervalVar({ length: unbuild_temp_pier })
    deck[n] = IntervalVar({ length: position_deck })
}

///////////////
// Objective //
///////////////

model.minimize(everything_else.end)

/////////////////
// Constraints //
/////////////////

// Deck is built on top of piers and after previous deck
for (let i = 0; i < n; i++) {
    if (i > 0) deck[i - 1].endBeforeStart(deck[i])
    pier[i].endBeforeStart(deck[i])
    temp_pier[i].endBeforeStart(deck[i])
    if (i > 0) pier[i - 1].endBeforeStart(deck[i]) // pier[-1] is the abutment
}

// Temporary pier is a unique resource
for (let i = 0; i < n; i++) {
    temp_pier[i].endBeforeStart(disassemble_temp_pier[i])
    deck[i].endBeforeStart(disassemble_temp_pier[i])
    if (i > 0) disassemble_temp_pier[i].endBeforeStart(temp_pier[i])
}

// Setup abutment and construction side before decks are built
for (let i = 0; i < n; i++) abutment.endBeforeStart(deck[i])

// Pylons and stays
for (let i = 0; i < n; i++) deck[i].endBeforeStart(everything_else)

///////////
// Solve //
///////////

CP.solve(model)

tip

It is very tempting in JavaScript to write the constraints in an enormous single for loop given that it each constraint start with one. We strongly recommend not doing it. The performance improvement is negligible for an important loss of readability

It just as tempting to adopt an interleaved style that alternates between variable definitions and constraints. We strongly advice against it, per experience people get lost in larger models written this way.

Generally speaking the free form and verbosity of JavaScript / Typescript models is a lurking danger that comes back to bite you once the project has grown and multiple people are working on it.

---

Exercise

Move the the tasks in the gantt chart until you find the optimal schedule for the Millau viaduct with a minimum lateness objective. We have limited the problem to 3 decks to make it simpler and make the gantt smaller.

Benchmarks

There are many variants of the project scheduling problem. The bechmmark section of the website explains the context in which each variant appears, and provides benchmark data as well as the current OptalCP results.