# Compute overlapping time

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

• 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? Aug 15 at 19:50

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