# Modelling precedence relations

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?

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}

• Rob, thank you very much for your reply and the suggestion. I will try both the Big-M and the Indicator Constraint approach. – Clement Apr 12 at 8:43

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