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 own time 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}

I would like to compute the time between all the pairs of tasks. That is, $s_j-e_i$ (if $i$ is scheduled before $j$) or $s_i-e_j$ (if $j$ is scheduled before $i$).

The objective is to minimize the times between all the pairs of tasks. How can I define it?

$\endgroup$
2
  • $\begingroup$ Do you have a single resource or multiple ones? Is there any relationship between the tasks? $\endgroup$
    – A.Omidi
    Nov 15, 2023 at 11:41
  • $\begingroup$ Only one resource is considered. Furthermore, tasks are independent. $\endgroup$ Nov 17, 2023 at 16:35

1 Answer 1

1
$\begingroup$

What you could do is the following: Introduce variable $t_{ij}$ that is the time between tasks $i$ and $j$. This variable is only defined for once per pair $ij$, therefore the $j >i$. Then, you can write:

\begin{align} \ & \min \sum_{i \in S}\sum_{j \in S, j>i} t_{ij} \; \\ \end{align}

and adding the following two constraints:

\begin{align} & s_j - e_i \leq t_{ij} & \forall i,j \in S, j>i \tag1 \\ & s_i - e_j \leq t_{ij} & \forall i,j \in S, j>i \tag2 \\ \end{align}

$\endgroup$
1

Your Answer

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

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