7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

gantt view within CPLEX IDE

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:

enter image description here

$\endgroup$
2
  • $\begingroup$ I am actually using CPOptimizer! Would this still be a good approach if there was around 30 pairs of sets of 10 tasks each ? Does the cardinality of the sets and the number of pairs of sets could change the choice of which modelisation to use for this constraint ? Thanks! $\endgroup$ Oct 15 at 20:09
  • $\begingroup$ You should try the state function approach then $\endgroup$ Oct 16 at 0:12
7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Would this still be a good approach if there was around 30 pairs of sets of 10 tasks each ? Does the cardinality of the sets and the number of pairs of sets could change the choice of which modelisation to use for this constraint ? Thanks! $\endgroup$ Oct 15 at 20:05
  • $\begingroup$ Yes, the cardinalities could change which model performs best. Are your durations and start times integer or arbitrary? $\endgroup$
    – RobPratt
    Oct 15 at 20:57
  • $\begingroup$ Durations are integer, they are given ($d_t$) while start time are variables. $\endgroup$ Oct 15 at 21:29
  • $\begingroup$ In that case, I suspect that the generalization of @worldsmithhelper's model to multiple pairs of groups (instead of just one pair $(1,2)$) would do better. $\endgroup$
    – RobPratt
    Oct 15 at 21:39
4
$\begingroup$

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$$

$\endgroup$

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.