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.
