3
$\begingroup$

Suppose we have $n$ tasks. These tasks can not be executed at the same time i.e. every task should be finished before starting the next task. Every task ($i=0,\cdots,n$) has a day in which it starts $s_i$, has execution time $t_i$ and a day in which the task "has" to be finished $f_i$. A task can have a longer execution time which causes the task te be finished after the day it has to be finished. Our goal is to minimize the maximum of time the execution time exceeds $f_i$.

I couldn't seem to figure out how to formulate the constraint that only one task can be executed at once. This is what I came up with (which is only the objective function and one constraint);

Where $y=1$ if $(s_i+t_i)-f_i) > 0$, and $0$ otherwise.

\begin{align}\min\max&\quad(\sum_{i=0}^{n}((s_i+t_i)-f_i)y)\\\text{s.t.}&\quad(s_i+t_i) \leq s_{i+1}\end{align}

Where we have that (I thought this was most straightforward) all $s_i,t,i$ and $f_i$ are integers and counted on the real line. So for example today is day 0 where as next week on monday we are day 7.

Anyone have any idea how to formulate this LP problem?

$\endgroup$
6
  • $\begingroup$ Are s,t,f constants, I mean given for a task or are any of these to be part of the solution? If these are decision variables your constraint ensures tasks are sequential except you can make $s_i + t_i \le s_j \ j \neq i$. $\endgroup$ Commented Dec 4, 2022 at 12:57
  • $\begingroup$ As for y_i as indicator of delay, it's like $s_i + t_i - f_i \le My_i$ and another constraint $f_i - (s_i+t_i) \le M(1-y_i)$. M can be just as large as what you can guess as final day(number) of the entire project. $\endgroup$ Commented Dec 4, 2022 at 13:06
  • $\begingroup$ @Sutanu, Yes s,t, and f are constants I presume. Otherwise I do not know how to model it if we work with dates. $\endgroup$ Commented Dec 4, 2022 at 13:09
  • $\begingroup$ It is not given though that s,t, and f are constants. This is just what I thought to be helpful, but maybe this doesn't make sense at all. $\endgroup$ Commented Dec 4, 2022 at 13:12
  • $\begingroup$ Yes I think this solves my problem, thank you very much for pointing it out! $\endgroup$ Commented Dec 4, 2022 at 14:23

1 Answer 1

2
$\begingroup$

First of all, I have to state that I do not know how to formulate your problem as an LP model. However, I do know how to make it through an IP model. Thus, I will proceed with this strategy.

Problem definition

Firstly, we will define our Non-Multitask Problem (NMP). An NMP instance is defined below. Let

  • $T$ be the set of $n$ tasks;
  • $s_i \in \mathbb{R}$ be the task $i \in T$ starting time;
  • $t_i \in \mathbb{R}$ be the task $i \in T$ execution time; And
  • $f_i \in \mathbb{R}_{\geqslant s_i}$ be the task $i \in T$ "desired" ending time.

An NMP solution is defined as a function $g: T \rightarrow \mathbb{R}$, where $g(i)$ stands for the task $i \in T$ ending time. A feasible NMP solution must satisfy the following rules:

  • $g(i) \geqslant s_i + t_i$, i.e. task $i$ ending time must encompass its task starting and execution times, $\forall i \in T$; And
  • $g(j) \geqslant g(i) + t_j \vee g(j) \leqslant g(i) - t_i$, i.e. two distinct tasks cannot share the same execution time, $\forall i, j \in T: i\neq j$.

The cost of an NMP solution is given by the function $c(g) = \sum_{i \in T} \max \{0, g(i) - f_i\}$, i.e. the cost is the sum of all exceding times.

IP model

Before moving to the model, let's take a look at some properties of this problem. If we consider

  • A dummy deposit task $d$;
  • An unweighted complete digraph $D(V = T \cup \{d\}, A = \{ (i, j) : i, j \in V \wedge i \neq j \})$, such that each task $i \in V$ is a node;
  • Parameter $t_i$ as the node $i \in T$ service time; And
  • Parameters $s_i$ and $f_i$ as node $i \in T$ time windows $[s_i, f_i]$.

We have a VRPTW variant, in which the goal is to find a hamiltonian tour in $G$ such that starting times $s$ are respected, and whose sum of all exceding times is minimized.

With this insight, we move to the modeling of the problem. Below follows the list of variables:

  • $y_i \in \mathbb{R}$ be the task $i \in V$ ending time;
  • $z_i \in \mathbb{R}^{+}$ be the task $i \in V$ exceeding time; And
  • $x_{ij} \in \mathbb{B}$ be the variable stating whether task $i$ immediately precedes task $j: (i, j) \in A$.

We will have the following objective function.

$\min \sum_{i \in T} z_i$ (1)

And the following constraints.

Task $i \in T$ exceeding time formula. Note that, by the definition of $z$, $z_i \geqslant 0$.

$z_i \geqslant y_i - f_i$ $\forall i \in T$ (2)

Task $i \in T$ ending time lower bound.

$y_i \geqslant s_i + t_i$ $\forall i \in T$ (3)

Reset dummy task $d$ ending time.

$y_d = 0$ (4)

Routing flow constraints, that force each task to precede another task.

$\sum_{a \in \delta^+(i)} x_a = \sum_{a \in \delta^-(i)} x_a = 1$ $\forall i \in V$ (5)

The MTZ connectivity constraints, guarantee that all feasible solutions will be hamiltonian paths in $D$. Such that the big-$M$ is equals to $\max_{i \in T} \{ s_i \} + \sum_{i \in T} t_i$.

$y_j \geqslant y_i + t_j - (1 - x_{ij}) M$ $\forall (i, j) \in A$ (6)

And finally the domain constraints.

$z \in \mathbb{R}^{+|V|}$ (7)

$y \in \mathbb{R}^{|V|}$ (8)

$x \in \mathbb{B}^{|A|}$ (9)

Case any point is not clear, please let me know.

$\endgroup$

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