3

I am working with integer optimization. I have a problem with $t$ tasks and every task $i$ needs $w_i$ weeks to be completed and $p_{il}$ workers on a specific week $l$. There is a total time in weeks to complete all tasks. I need to optimize (min) the max value of workers needed in any week (variables to define: starting week for every particular task, or similar). Weeks needed per task and amount of workers in each week are given as data points.

There is also a constraint: once a task starts, it should be finished (can't be paused). All tasks could run in parallel if needed.

How can I model this optimization problem formally?

N Fp
  • 33
  • 4
  • 3
    We generally ask that posters show what work they have done so far, rather than just producing a full solution deus ex machina. – prubin Jul 20 '21 at 21:24
  • The notations are ambiguous, as the index $t$ refers to the amount of tasks, and a given week (if I understand correctly). – Kuifje Jul 21 '21 at 07:46
  • Yes @Kuifje. Thanks for that. I've already fixed it. – N Fp Jul 21 '21 at 10:13
  • Why does a task require a different amount of workers depending on the week ? – Kuifje Jul 21 '21 at 10:20
  • The amount of work needed is not constant, and variable depending on each task as well. It make sense if we think for example than the tasks are different software development projects (which involve different teams and effort depending on the needs). – N Fp Jul 21 '21 at 11:02
  • I really support that approach @prubin but I'm quite confused at this moment and I couldn't manage to formulate something coherent. I'm continue working on this and I'll add any improvement if get it. – N Fp Jul 21 '21 at 11:07
  • @MFp to help you get started : 1/ define your variables (when should you start a task ?) 2/ write the objective function in terms of these variables 3/ list all of the constraints you can think of (in plain english to start with). This will help you understand the process, and the solution (if someone posts one) – Kuifje Jul 21 '21 at 11:16
  • This is quiet similar a problem i solved for someone else here. Please take a look if you can change up this scheme to make it work for you. https://or.stackexchange.com/a/6236/4777 the minimize upper bound of all weeks trick will work here. How to implement the work in uninterrupted is discussed in the comments – worldsmithhelper Jul 21 '21 at 12:45

1 Answers1

5

Well, you did not define and detail well the problem, hence, I will first write formally the problem definition based on my understanding of what you have written, and then I will propose an Integer Programming formulation.

Problem definition

Let's first define formally the problem. Let:

  • $t$ be the number of tasks to be serviced;
  • $T = \mathbb{N}_{\leqslant t}^{*}$ be the set of tasks to be serviced;
  • $m$ be the number of available weeks;
  • $M = \mathbb{N}_{\leqslant m}^{*}$ be the set of available weeks;
  • $w_i \in \mathbb{Z}$ be the number of weeks the task $i \in T$ requires;
  • $p_{il} \in \mathbb{Z}$ be the number of workers the task $i \in T$ requires in week $l \in M$.

A feasible solution for this variant of the classical scheduling problem is given by an allocation of the tasks in $T$ in the weeks of $M$ in a way that, if the task $i \in T$ starts to be executed in the week $l \in M: l \leqslant m - w_i + 1$, then the task $i$ will be allocated, in order to guarantee the continuity of the task execution, on the weeks in {$l^{'} \in M: l \leqslant l^{'} < l + w_i$}. An optimal solution for this variant is a feasible solution in which the maximum amount of workers used in any week is minimum.

An Integer Programming formulation

Let's consider the variables

$$ x_{il} = \begin{cases} 1 &\text{if task $i \in T$ is executed in week $l \in M$,}\\ 0 &\text{otherwise} \end{cases}, \\ z_{il} = \begin{cases} 1 &\text{if task $i \in T$ starts to be serviced in week $l \in M : l \leqslant m - w_i + 1$,}\\ 0 &\text{otherwise} \end{cases}, \\ \text{and} \\ y \in \mathbb{Z} \text{ is the number of workers that the week with the} \\ \text{maximum number of workers has in a feasible solution}. $$

Below follows the IP formulation.

Objective Function: $$ \text{min } y $$

Constraints:

The variable $y$ assumes a value greater than or equals to the number of workers used in each week.

$$ y \geqslant \sum_{i \in T} p_{il} x_{il} \quad \forall l \in M; $$

If the task $i \in T$ begins to be serviced in the week $l \in M : l \leqslant m - w_i + 1$, then this task will be allocated to all the weeks in $\{l^{'} \in M : l \leqslant l^{'} < l + w_i\}$.

$$ z_{il} = x_{il^{'}} \quad \forall i \in T, \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \forall l \in M : l \leqslant m - w_i + 1, \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \forall l^{'} \in M : l \leqslant l^{'} < l + w_i; $$

A task $i \in T$ must start to be serviced in exactly one feasible week, i.e., one week between $1$ and $m - w_i + 1$.

$$ \sum_{l \in M : l \leqslant m - w_i + 1} z_{il} = 1 \quad \forall i \in T. $$

If you want to consider a serial, non-parallel, version of the problem. You can add the following set of constraints to the formulation.

$$ \sum_{i \in T} x_{il} \leqslant 1 \quad \forall l \in M. $$

If anyone has any question or have found any error, please let me know.