Compute overlapping time

Question

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

Answer 1

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