How to make this mathematical modeling linear?

Question

The problem I'm dealing with has the objective to minimize the amount of people we need to hire. We have 14 contracts with 14 companies, each of which have shared with us the amount of workers that they need for their projects (different for every company) as well as the time that each project shall take in weeks. We have 24 at our disposal to provide the services, meaning that all projects must be completed in the following 24 weeks.

I have created a mathematical modeling by saying that $x_i$ is the starting week of project $i$, $t_i$ is the weeks that are required for the project and $c_i$ are the number of workers needed for project $i$ (by company $i$). Furthermore, if project $i$ is taking place during week $j$, the binary variable $Y_{ij}=1$ and $0$ otherwise.It can be presented as: $$Y_{ij}=\begin{cases} 1 & if \quad x_i \leq j < x_i + t_i, i=1,...,14, j=1,...,24 \\ 0 & otherwise \end{cases}$$

With the variable $W_j$ I represent the amount of workers that will be working on week $j$, where $W_j=\sum_{i=1}^{14} Y_{ij}\cdot c_i,$ $j=1,...,24$.

My objective function is $minW=max_{\{1\leq j\leq 24\}}W_j$ and the sole constraint whould be $1\leq x_i \leq 24 -t_i +1$.

I have been trying to find a way to make this modeling linear, but I have failed so far. I am also trying to find the solution to this using Excel Solver by having $x_i$ as the decision variables. I tried to make $x_i$ into $x_{ij}$ to indicate that if $x_{ij}=1$ then that means week $j$ is the starting week of project $i$, but that is going to turn into too many variables and I know that it can be done without complicating it that much. Can someone help me?

Answer 1

Let binary decision variable $x_{ij}$ indicate whether project $i$ starts in week $j\in\{1,\dots,25-t_i\}$. If $x_{ij}=1$, then project $i$ uses $c_i$ workers in weeks $\{j,\dots,j+t_i-1\}$. So the number of workers used across all projects in week $j$ is $\sum_{i=1}^{14} c_i \sum_{k=\max(1,j-t_i+1)}^j x_{ik}$. The problem is to minimize $z$ subject to \begin{align} \sum_{j=1}^{25-t_i} x_{ij} &= 1 &&\text{for $i\in\{1,\dots,14\}$} \\ z &\ge \sum_{i=1}^{14} c_i \sum_{k=\max(1,j-t_i+1)}^j x_{ik} &&\text{for $j\in\{1,\dots,24\}$} \end{align}