5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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}

$\endgroup$
1
  • $\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
5
$\begingroup$

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

view of seq in CPLEX IDE

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This however, will function only in the case of a discrete time formulation? Why is this formulation tighter? $\endgroup$
    – Clement
    Jul 7 at 8:31
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Jul 7 at 9:54

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.