3
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ We generally ask that posters show what work they have done so far, rather than just producing a full solution deus ex machina. $\endgroup$
    – prubin
    Jul 20, 2021 at 21:24
  • $\begingroup$ The notations are ambiguous, as the index $t$ refers to the amount of tasks, and a given week (if I understand correctly). $\endgroup$
    – Kuifje
    Jul 21, 2021 at 7:46
  • $\begingroup$ Yes @Kuifje. Thanks for that. I've already fixed it. $\endgroup$
    – N Fp
    Jul 21, 2021 at 10:13
  • $\begingroup$ Why does a task require a different amount of workers depending on the week ? $\endgroup$
    – Kuifje
    Jul 21, 2021 at 10:20
  • $\begingroup$ 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). $\endgroup$
    – N Fp
    Jul 21, 2021 at 11:02

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ It's a really good formulation!. I could not find any error or improvement, thanks! $\endgroup$
    – N Fp
    Jul 27, 2021 at 0:16
  • $\begingroup$ @NFp you are welcome. $\endgroup$ Jul 27, 2021 at 2:38
  • $\begingroup$ @NFp just for curiosity, have you seen this problem in any scientific paper? $\endgroup$ Jul 27, 2021 at 20:15

Your Answer

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

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