How to model a non-overlap constraint between 2 groups of tasks?

Question

Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$.

Let $T_1 \subset T$ and $T_2 \subset T$ such as $T_1 \cap T_2 = \emptyset $

How can I model the following constraint : all tasks from $T_1$ cannot overlap all tasks of $T_2$ and vice versa. So basically, tasks from a same set can overlap but when a task from a set is performed, no task from the other set can overlap it.

Answer 1

within CPLEX you could try CPOptimizer and use intervals.

In OPL (One of CPLEX API) you could write

using CP;
int sizeT=10;
range T=1..sizeT;
int d[i in T]=i;

dvar interval t[i in T] size d[i];

{int} T1={i | i in T : i <=(sizeT div 2)};
{int} T2=asSet(T) diff T1;

subject to
{
  forall(i in T1,j in T2) overlapLength(t[i],t[j])==0;
}

and then see

This works and is a bit naive.

So a better way as far as solve speed is concerned is to rely on state functions:

using CP;
int sizeT=10;
range T=1..sizeT;
int d[i in T]=i;

dvar interval t[i in T] size d[i];

{int} T1={i | i in T : i <=(sizeT div 2)};
{int} T2=asSet(T) diff T1;

stateFunction s; // 1 or 2 according to T1 or T2

subject to
{
 
  forall(i in T1) alwaysEqual(s,t[i],1);
  forall(i in T2) alwaysEqual(s,t[i],2);
}

which will do the same but faster.

And you can see in the CPLEX IDE for s:

Answer 2

One simple approach is to impose the classical non-overlap constraints for each pair of tasks for which one task is in $T_1$ and one task is in $T_2$, as shown here.

Answer 3

I assume for you have a binary matrix $S_{i,t}$ (tasks)$\times$(time steps) which tells you whether some task $i$ is active at time $t$. This approach introduces additional variables unless you have other parallelism constraints that can only be expressed in that format or of your objective depends on it like it does here.

Define a new binary matrix of $G_{g,t}$(task groups)$\times$(time steps) and impose the constraints:

$$\forall t_i\in T_1 \forall t\in\text{Time}: S_{i,t} \leq G_{1,t} $$

and similar for $T_2$. $G_{1,t}$ will be $1$ if any of the tasks in $T_1$ are active. Now you can express constraints on which groups can be active at time $t$. In your case you want:

$$\forall t\in\text{Time}: G_{1,t} + G_{2,t} \leq 1$$