Formulation as Constraint Program (CP)

We formulate the RLSP into a constraint program using constructs available in OR-Tools.

Definition of Variables

For operations, we use interval variables. An interval variable is defined as:

\[ i = (i_s, i_d, i_e, i_p) \]

consisting of integer values for:

  • start: \(i_s\)

  • duration: \(i_d\)

  • end: \(i_e\)

  • presence: \(i_p \in \{0, 1\}\)

The presence variable indicates whether the interval is active (i.e., part of the solution) or ignored by all constraints. Introducing an interval variable implicitly enforces:

\[ i_s + i_d = i_e \]

To handle the assignment of machines (especially with multiple identical machines) and to simplify constraint formulation, we introduce roles of machines in operations.

Let \(o \in O\) be an operation. The roles in \(o\) are defined as:

\[\begin{split} R(o) := \begin{cases} (\text{origin, main, target}) & \text{if } o \in \hat{O} \text{ (move operations)} \\ (\text{main}) & \text{if } o \notin \hat{O} \end{cases} \end{split}\]

The set of machines in a machine configuration \(L\) that can fulfill the main role is denoted:

  • If \(\hat{M}(o)\) is defined:

\[ \tilde{M}(o, \text{main}) = \{ \hat{M}(o) \} \]

  • Otherwise:

\[ \tilde{M}(o, \text{main}) = \{ M \in L \mid T(M) = T(o) \} \]

We now formalize the assignment of machines to roles in an operation.

For each operation \(o \in O\) with roles \(R(o)\), define the set of feasible role assignments in machine configuration \(L\):

\[ R_L(o) := \prod_{R \in R(o)} \tilde{M}(o, R) \]

Each \(r \in R_L(o)\) is a mapping:

\[ r: R(o) \to \tilde{M}(o, R) \]

assigning each role \(R\) to a machine \(r(R) \in \tilde{M}(o, R)\). Each assignment represents one way to execute the operation using available machines.

Each operation \(o \in O\) is represented by a finite set of interval variables:

\[ I_o = \{ (s_o, d_o, e_o, p_r) \mid r \in R_L(o) \} \]

  • \(s_o\), \(e_o\): start and end variables of \(o\)

  • \(d_o\): known duration

  • \(p_r \in \{0,1\}\): presence variable for assignment \(r\)

Explanation of Used Constraints

Consistency Constraints

Only one assignment of machines to roles must be chosen:

\[ \sum_{r} p_r = 1 \quad \text{for all } o \in O \]

In OR-Tools:

model.AddExactlyOne(p_r_list)

If operations \(o_i\) and \(o_j\) are connected and share a role, presence variables must agree:

\[ p_{r_i} = p_{r_j} \]

In OR-Tools:

model.Add(p1 == p2)

Precedence Constraints

For each edge \(e = (o_i, o_j) \in E\):

\[ w_{\min}(e) \leq s_{o_j} - e_{o_i} \leq w_{\max}(e) \]

In OR-Tools:

model.Add(end_i <= start_j)
model.Add(start_j - end_i >= wmin)
model.Add(start_j - end_i <= wmax)

Processing Capacity Constraints

Each machine \(M \in L\) has capacity \(c_p(M)\):

  • If \(c_p(M) = 1\): enforce no overlap:

    model.AddNoOverlap(intervals)

  • If \(c_p(M) > 1\): allow overlaps up to capacity:

    model.AddCumulative(intervals, demands, capacity)

Spatial Capacity Constraints

Machines have spatial capacity \(c_s(M)\). Model storage via reservoir constraints:

  • Transport into \(M\): increase level at \(s_o\)

  • Transport out of \(M\): decrease level at \(e_o\)

In OR-Tools:

model.AddReservoirConstraintWithActive(
    times, level_changes, actives, min, max
)

No Load-While-Processing Constraints

Machines with \(l(M) = 0\) can’t load/unload during processing:

\[ [s_1, e_1) \cap [s_2, e_2) = \emptyset \]

In OR-Tools:

model.AddNoOverlap([I_1, I_2])

Objective Function and Waiting Costs

Objective: minimize weighted sum of waiting costs and makespan:

\[ \text{Cost}_\alpha(S) := \text{WaitCost}(S) + \alpha \cdot \text{Makespan}(S) \]

Makespan:

\[ \text{makespan} := \max_{o \in O} e_o \]
model.AddMaxEquality(makespan, [e_o])

Waiting Costs:

  • For edge \((o_i, o_j)\):

    \[ w_{ij} := c(e) \cdot (s_{o_j} - e_{o_i}) \]

  • For initial operation:

    \[ w_o := c_o \cdot s_o \]

Total:

\[ \text{wait_cost} := \sum w_{ij} + \sum w_o \]

Final objective:

model.Minimize(alpha * makespan + wait_cost)

Soft Constraints (Optional)

To allow bounded violations:

\[ \xi_k \geq (s_{o_j} - e_{o_i}) - w_{\max}(e) \quad \text{or} \quad \xi_k \geq w_{\min}(e) - (s_{o_j} - e_{o_i}) \]

Final objective (with penalties \(\beta\)):

model.Minimize(alpha * makespan + wait_cost + beta * sum(aux_vars))

Discussion of the CP Model

Rescheduling

It is possible to reoptimize partially executed schedules after for example durations differed from the expectation. This can be done by simply fixing the starting and ending time as well as machine assignments of corresponding intervals.

Including Heuristics

Ortools offers the syntax of solution hints. That allows attempts to compute sulotions with different heuristics and feed the solutions into ortools which then tries to improve that solution.

Performance

CP has proven to be better than MIP. One can roughly expect reasonable solutions on a average computer within 1 minute to problems of up to 80 operations.