2
$\begingroup$

I am trying to solve an optimization problem in which there is a set of tasks, $S$, where $s_i$ and $e_i$ are the starting and ending time of task $i \in S$. Each task $i $ must be done within its time own window $[a_i, b_i]$: \begin{equation} a_i \le s_i, \forall i \in S \end{equation} \begin{equation} e_i \le b_i, \forall i \in S \end{equation}

Due to the presence of time windows, tasks could overlap. I have defined continuous variable $t_{ij}$ to quantify the overlapping time of tasks $i$ and $j$.

The objective is to minimize the overlapping time: \begin{equation} min \sum_{i,j \in S} t_{ij} \end{equation}

How can I define constraints to compute $t_{ij}$?

$\endgroup$
1
  • $\begingroup$ Welcome to OR.SE. Do you have a single resource to process the tasks or there are multiple resources? Is it possible to have no overlap or this is mandatory? $\endgroup$
    – A.Omidi
    Aug 15 at 19:50

1 Answer 1

3
$\begingroup$

First note that you can omit $t_{ij}$ for any pair $(i,j)$ for which the time windows do not overlap because $t_{ij}=0$ in that case.

Tasks $i$ and $j$ overlap if and only if the later starting time $\max(s_i,s_j)$ precedes the earlier ending time $\min(e_i,e_j)$, so you want to enforce $$t_{ij} \ge \max(\min(e_i,e_j) - \max(s_i,s_j), 0),$$ which can be linearized by introducing $u_{ij}$ to represent $\max(s_i,s_j)$, $v_{ij}$ to represent $\min(e_i,e_j)$, binary variables $x_{ij}$ and $y_{ij}$, and linear constraints: \begin{align} 0 \le u_{ij} - s_i &\le (b_j-a_i) y_{ij} \tag1\label1\\ 0 \le u_{ij} - s_j &\le (b_i-a_j) (1-y_{ij}) \tag2\label2\\ (a_j-b_i) x_{ij} \le v_{ij} - e_i &\le 0 \tag3\label3\\ (a_i-b_j) (1-x_{ij}) \le v_{ij} - e_j &\le 0 \tag4\label4\\ t_{ij} &\ge v_{ij} - u_{ij} \tag5\label5 \\ t_{ij} &\ge 0 \tag6\label6 \end{align} Constraints \eqref{1} and \eqref{2} enforce $u_{ij}=\max(s_i,s_j)$. Constraints \eqref{3} and \eqref{4} enforce $v_{ij}=\min(e_i,e_j)$. Constraints \eqref{5} and \eqref{6} enforce $t_{ij}\ge\max(v_{ij}-u_{ij},0)$.

$\endgroup$
3
  • $\begingroup$ Does this require the introduction of binary variables? $\endgroup$
    – prubin
    Aug 15 at 15:49
  • $\begingroup$ @prubin Yes, it does. $\endgroup$
    – RobPratt
    Aug 15 at 16:02
  • $\begingroup$ @RobPratt thank you very much for your help. It works perfectly :) $\endgroup$ Aug 16 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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