# 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. Apr 12 at 8:43

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.

• This however, will function only in the case of a discrete time formulation? Why is this formulation tighter? Jul 7 at 8:31
• Yes indeed this assumes a discrete time span. That seems reasonable to me. I don't think it is easy to prove that the formulation is tighter - this could be a great separate question. I only have empirical evidence to back this statement. Jul 7 at 9:54

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