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}

  • $\begingroup$ Rob, thank you very much for your reply and the suggestion. I will try both the Big-M and the Indicator Constraint approach. $\endgroup$ – 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.


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

the constraint


makes sure that i and k do not overlap

and in the CPLEX IDE you will see

view of seq in CPLEX IDE


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.