Modelling precedence relations

Question

I have two tasks $i$ and $k$ with durations $d_i$ and $d_k$, where $d_i$ and $d_k$ are nonnegative variables.

I would like to model that $i$ may precede $k$ or $k$ may precede $i$ and that they may not overlap.

So, with $t_i$ and $t_k$ denoting the start times of $i$ and $k$, I have to model:

either $t_i + d_i \le t_k$ OR $t_k + d_k \le t_i$

Introducing a binary variable $y$, I can achieve the result with the following two big M constraints:

$t_i + d_i - t_k \le M y $

$t_k + d_k - t_i \le M (1-y)$

If it is required that $t_i + d_i \le H $ and $t_k + d_k \le H $ then I can set $M$ to be $M=H$.

My question is, is what I have done so far correct (what worries me is the variable duration) and can anyone think about a better formulation?

Answer 1

You may also use CPOptimizer within CPLEX that contains scheduling high level concepts. And then you can directly use noOverlap constraints.

In

using  CP;
dvar interval i size 5;
dvar interval k size 4;
dvar sequence seq in append(i,k);
minimize maxl(endOf(i),endOf(k));
subject to
{
  noOverlap(seq);
}

the constraint

noOverlap(seq);

makes sure that i and k do not overlap

and in the CPLEX IDE you will see

Answer 2

Can anyone think about a better formulation?

Another option is to use binary variables $x_{it}$ that take value $1$ if task $i$ starts at time $t$. You then need two sets of constraints:

• one start time per task: $$ \sum_{t}x_{it} = 1 \quad \forall i $$
• don't overlap tasks: $$ \sum_{i}\sum_{k, t+1 - d_i \le k \le t}x_{ik} \le 1 \quad \forall t $$

This formulation is more tight and should solve faster. And it does not require big-Ms.

Answer 3

Yes, this is correct and is the classical approach from Manne, On the Job-Shop Scheduling Problem (1960).

In some modeling languages, you can also enforce these implications by using indicator constraints: \begin{align} y = 0 &\implies t_i + d_i \le t_k \\ y = 1 &\implies t_k + d_k \le t_i \\ \end{align}