How to approach this shifts problem with Excel Solver?

Question

I am trying to find a way to solve the following problem of mine by using Solver but I get stuck right at the end of it.

I have a table of 14 companies each of which want to work on a project. I will be providing them with the workers that are required. In a table I have the workers that each company needs and the amount of time in weeks that their project will take. Once the workers are assigned they can't leave their post. Based on all this information (and the table) I have to calculate the least amount of workers that my company needs to hire for all projects to be completed within 6 months.

Now, for the sake of space and time, I'll reduce this problem to 4 companies to give you my POV:

Company   Workers required   Weeks required
A                 3                3
B                 1                3
C                 5                2
D                 4                3

Suppose that there's no obvious answer to this and that we have 2 months in our disposal, or something like that. 2 months have approx 8 weeks and so the above projects need to be completed in 8 weeks.

My mathematical modeling is as follows: Let $x_i $ be the week that project $i$ starts. Also, $t_i$ shall be the weeks required for project $i$ and $c_i$ will be the workers required.

Furthermore, I'll have $Y_{ij}$ be a binary variable that is equal to 1 if project $i$ is taking place during week $j$ and 0 if not. Thus, $W_j=\sum_{i=1}^{4}Y_{ij}\cdot c_i$ is the amount of workers that are working during week $j$.

Therefore, we are looking to minimize $W=max_{1\leq j\leq 8}W_j$.

The only constraint I believe there is the following: $1\leq x_i \leq 8-t_i+1$ meaning that a project can start on the 1st week at least and be completed by the end of the 8th week at most.

Now,I have taken this to Excel and have created 2 tables. One that has the companies column and the values $t_i$, $x_i$ and $x_i+t_i$ for each one. On another column I have the restraint that $x_i\leq 8-t_i+1$ that I would use for solver. On the second table I have the companies, $t_i$, $c_i$, and 8 columns one for each week.The variables on the inside represent $y_{ij}$ and at the end of each column I have calculated the sumproduct of $c_i$ with column $j$ meaning the $W_j$'s. Finally, my target cell is the maximum of the $W_j$'s.

When I try to run Solver with the $x_i$'s as the changing variable cells it returns an error that the problem is not linear (my $Y_{ij}$'s are set to either 1 or 0 with an IF function depending on $x_i$'s values), but when I go use $Y_j$'s as the changing variable cells, other than the fact that I don't know how to include the constraint, it just keeps every variable at 0 without giving me a solution. Mind you, my table has more companies and weeks (14com $\times$ 24w) which exceeds the 200 variables that Solver can handle.

How am I approaching this wrong? What steps should I take/change in my process to find the solution to my problem?

Edit: I’ve decided to accept every answer as correct, because they were all so well presented and helped me learn something new and see the solution to this from different perspectives. Thank you all for your precious time and help!

Answer 1

1. I very much doubt that Solver knows how to convert an IF function into a linear constraint (although I suppose it is possible). So I think you need to rethink your MIP model.
2. If the variable limit in Solver becomes an obstacle, you can install OpenSolver, which is an open-source (hence free) Excel add-in that extends the capabilities of Solver.

Addendum: One way to avoid the "if" statement is to change $x_i$ to binary variables $x_{ij},$ where $x_{ij} = 1$ if and only if project $i$ begins in week $j$. You would add the constraint $$\sum_{j=1}^{9-t_i} x_{ij} = 1 \quad\forall i$$ to ensure that each project is assigned a single start time, and the constraints $$Y_{ij} = \sum_{k=\max(1,j-t_i + 1)}^j x_{ik} \quad \forall i,j$$ to define $Y$ in terms of the start time variable.

Answer 2

First of all, you will have to ensure that the total number of weeks is enough to schedule, otherwise, it causes many overlaps in projects. The mentioned problem can be formulated either as a resource-constrained project schedule or a variant of aggregation planning or through Monte Carlo simulation to examine how many resources you actually need. The first and the second would be as follows:

1- Resource-constrained project schedule:

One of the best approaches to solving such an assignment problem, specifically when it comes along with a variation in the different resources, is project scheduling tools. In the following, two scenarios are depicted. First, by assuming to execute projects $1,2$ simultaneously and $4, 5$ sequentially, and second by overlapping the projects and allowing to extend the resource availability in the time horizon.

• First

In this scenario, we have 9 identical resources. Each project can execute with whose resources except project$D$ that uses the shared resources.

• Second

In the second, I try with only $3$ resources with overlapping tasks. You can obviously see changing in the finish time after leveling/dispatching resources. I think this is a simple way to examine many different scenarios.

---

2- Aggregate planning:

Defining the sets $p \in Projects$, $w \in Weeks$, $ r \in Resources$, and parameters $Cost_{i,p}$, $Duration_{p}$, and $AvailableTime_{p}$, and declare decision variable $x_{r,p,t}$ to calculate the number of resources needed for each project at each week and the following model:

\begin{array}{l} \text{Minimize} & Z = \sum_{r,p,w} Cost_{r,p}x_{r,p,w}\\ \text{subject to:}& \\ &\sum_{r} AvailableTime_{p} x_{r,p,w} = Duration_{p} & \forall p \in Projects, w \in Week\\ &x_{r,p,w} \geq 0, \end{array}

Based on the data table in the original question and some random data the result is:

        VARIABLE x[r,p,w] 
 
                     w1          w2          w3          w4

worker_1.p1       3.000       3.000       3.000       3.000
worker_1.p4       3.000       3.000       3.000       3.000
worker_2.p2       1.000       1.000       1.000       1.000
worker_2.p3       3.000       3.000       3.000       3.000

I am not an Excel_solver user, but this template would be helpful to run it.

Answer 3

Well, to do min-max I think you need
Assuming project implies company

Minimize $z$
s.t.
$z \ge \sum_{i=1}^4 Y_{i,j}c_i \ \ \forall j$

$\sum_{j=1}^W Y_{i,j} = t_i \ \ \forall i$: where W = 9 (assigned total time)
$t_iY_{i,j-1} - \sum_{k=1}^{j-1} Y_{i,k} \le t_iY_{i,j}\ \ \forall j=2...W-1, \ \forall i$: Ensures Y's are consecutively assigned
$Y \in\ \{0,1\}^{i\times j} $

Images

Answer 4

Introduction

The problem consists in determining the optimal project start-up sequence, i.e. the sequence such as to minimize the number of workers hired without violating the time constraint imposed by the assignment of a worker to a certain project for a given number of weeks.

Enumerating all possible sequences

The project sequencing decision problem can be solved by listing all possible sequences, calculating the respective number of workers needed and selecting the sequence with the minimum number of hired workers. Given a graph having $T$≥1 levels and $N$ different projects, at each level $T$ there will be $N-T$ possible decisional alternatives. The number of sequences of projects admissible a priori is therefore equal to $N\cdot(N-1)\cdot(N-2)\cdot … \cdot (N-(T-1))$ For example, having assigned $N=14$ different projects and setting a planning horizon of $T=8$ weeks, the possible alternatives to be evaluated turn out to be $14\cdot13\cdot…\cdot7= 121,080,960$, a number certainly beyond a direct evaluation. Therefore, in practice visiting the decision tree is not feasible: the use of mathematical programming is fundamental.

The model

Unit of time

The decision-making problem of sequencing projects is implicitly discrete-time where the instants of occurrence of the events can be defined a priori. Events are the start point of a project, while its duration is assigned a priori. The events that occur in the mathematical model are variations in the value of some variable and these events can only occur at the extremes of one of the intervals with which the time horizon is divided. At the beginning or at the end of the interval itself. Since the activity planning calendar is weekly, the week is adopted as the unit of time. The time horizon $T$ is therefore divided into a certain number of intervals each with a time duration of one week.

Variables

The following model gives the starting temporal sequence for $N=14$ projects so that the number of hired workers is optimal within the planning horizon of $T=8$ weeks. The model requires $112$ Boolean variables ($112=14 \cdot 8$) and $8$ integers variables (1 integer variable for each week). Every week is designate by means of a pedice $i=1, 2, \ldots, T=8$.

For each week, the possible choices are basically two:

“start” or “not start” a project in the i-th week

We designate the projects by means of a pedice $j=1, 2,..., N$. As consequence, we need $T \cdot N = 8\cdot14 = 112$ variables in order to define all possible decisions. Let introduce the Boolean variable $x_{i,j}$

• $x_{i,j}=1$ if in i-th week I decide to start the project j-th and to keep $w_j$ workers as many weeks as required/specified for the j-th project
• $x_{i,j}=0$ if in i-th week I decide to not start the j-th project

Parameters

$w_j$: number of workers to be assigned to the j-th project

$t_j$: number of weeks needed to complete the j-th project

Constraints

We introduce $T=8$ equations and variables $A_i$ that track how long workers are kept for the future weeks.

$ A_1 = \sum_{i=1}^{N} t_j \cdot x_{1,j} $

$ A_2 = A_1 - 1 + \sum_{j=1}^{N} t_j \cdot x_{2,j} $

$ \vdots $

$ A_T = A_{T-1} - 1 + \sum_{j=1}^{N} t_j \cdot x_{T,j} $

For example, in the first week if we decide to start the $j=2$ project and to keep it for $t_2=3$ weeks it results: $ A_1 = \sum_{j=1}^{N} x_{1,j} \cdot t_k = 3$ because $x_{1,2}=1$ and $x_{1,1}=x_{1,3}= x_{1,4}=…= 0$. In order to impose in every week there is a project in execution, we add further $T$ constraints: $ A_i \geq 1 \quad \forall i=1,\ldots,T $.

In order to avoid the unacceptable situation of use a worker when the workers of the previous projects are not yet free and available, we introduce the following $T-1$ additional constraints as

$\left\{ \begin{array}{l} \sum_{j=1}^{N} t_j \cdot x_{1,j} \leq (1 - \sum_{j=1}^{N} x_{2,j} ) \cdot M +1 \\ A_{1} -1 + \sum_{j=1}^{N} t_j \cdot x_{2,j} \leq (1 - \sum_{j=1}^{N} x_{3,j} ) \cdot M +1 \\ \vdots \\ A_{T-2} -1 + \sum_{j=1}^{N} t_j \cdot x_{T-1,j} \leq (1 - \sum_{j=1}^{N} x_{T,j} ) \cdot M +1 \\ \end{array} \right. $

where the parameter M can be choosen as $M > \max_j t_j $

The constraint $\sum_{j=1}^{N} x_{i,j} \leq 1 \quad \forall i=1,\ldots,T $ makes sure that no any project is in execution in parallel with someone other. If parallel execution is allowable, this constraint can be removed.

The constraint $\sum_{i=1}^{T} x_{i,j} \leq 1 \quad \forall j=1,\ldots,N $ makes sure that every company executes no more than one project.

Finally, the constraint $\sum_{i=1}^{T} \sum_{j=1}^{N} t_j \cdot x_{i,j} \leq T$ makes sure that all selected projects are completed within the fixed planning horizon $T=8$.

Formulation as Linear Programming Model

$ min \left \{ \sum_{i = 1}^T \sum_{j = 1}^N w_j \cdot x_{i,j} \right \} $

Subject to

$\left\{ \begin{array}{l} A_1 = \sum_{i=1}^{N} t_j \cdot x_{1,j} \\ A_2 = A_1 - 1 + \sum_{j=1}^{N} t_j \cdot x_{2,j} \\ \vdots \\ A_T = A_{T-1} - 1 + \sum_{j=1}^{N} t_j \cdot x_{T,j} \\ \sum_{j=1}^{N} t_j \cdot x_{1,j} \leq (1 - \sum_{j=1}^{N} x_{2,j} ) \cdot M +1 \\ A_{1} -1 + \sum_{j=1}^{N} t_j \cdot x_{2,j} \leq (1 - \sum_{j=1}^{N} x_{3,j} ) \cdot M +1 \\ \vdots \\ A_{T-2} -1 + \sum_{j=1}^{N} t_j \cdot x_{T-1,j} \leq (1 - \sum_{j=1}^{N} x_{T,j} ) \cdot M +1 \\ \sum_{j=1}^{N} x_{i,j} \leq 1 \quad \forall i=1,\ldots,T \\ \sum_{i=1}^{T} x_{i,j} \leq 1 \quad \forall j=1,\ldots,N \\ \sum_{i=1}^{T} \sum_{j=1}^{N} t_j \cdot x_{i,j} \leq T \\ A_i \ge 1 \quad \forall i=1,\ldots,T \\ x_{i,j} \in \left \{ 0 ; 1 \right \} \forall \ i, j \end{array} \right. $

Remarks The computational capacity of Solver is artificially limited to a certain number of variables (200 variable cells, 2018). There is an open source software, OpenSolver, capable of solving optimization problems in the linear, integer and non-linear form in Excel that does not admit a maximum number of variables. OpenSolver uses COIN-OR CBC to generate the solution in Excel.