2
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ Would you please, 1) are the workers numbers pre-defined at the starting point for each project? 2) How many are the the total available number of workers at the beginning? 3) Is it possible to assign the maximum number of workers in each project to finish asap? 4) or there is something like due data/dead line to complete each of which? $\endgroup$
    – A.Omidi
    Dec 30, 2022 at 21:22
  • $\begingroup$ Sorry for the late reply, I just sat to rethink the problem. Well 1&2) The goal that I'm trying to achieve is determine the least amount of workers that I have to hire so they can do the projects. 3) Therefore, I can't just have all the projects be done starting on week 1 if that means I need 50ish workers which can be avoided. I don't know their salary but I want to reduce that as much as possible. 4) The due date for the project completion is 6 months and each project has about 2-4 weeks that it needs for completion. $\endgroup$
    – Tita
    Dec 31, 2022 at 15:35
  • $\begingroup$ Cross-posted: math.stackexchange.com/questions/4609417/… $\endgroup$
    – RobPratt
    Jan 2, 2023 at 1:10
  • $\begingroup$ @RobPratt Sorry, for doing that, I thought I tailored my question here to highlight that I need to use Excel for OR purposes and for the mathematical modeling in Maths. I am not allowed to delete my post because someone has answered. I didn’t see anything in the guidelines about this, what should I do? $\endgroup$
    – Tita
    Jan 2, 2023 at 12:03
  • $\begingroup$ @Tita With regards to your example, my proposed linear programming model suggest to assign project in the first week to B company, the 4th week to A Co., the 7th week to C Co. In total you need to hire 3 workers for firts 6 weeks and to add 2 workers for the last 2 weeks. I am available to share the excel template with you if any. $\endgroup$ Jan 3, 2023 at 12:48

4 Answers 4

2
$\begingroup$
  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.

$\endgroup$
9
  • $\begingroup$ I believe that you are right in your 1st point, but I have no idea how to define the $Y_{ij}$ variables otherwise. It is clear to me that my changing variables are $x_i$, so I am having trouble solving this. As far as the 2nd point goes, I have already installed OpenSolver from what I found online about exceeding the variable limit, but I doubt that's the problem since I've already found a similar problem in a book that uses Solver and has the same modeling as mine. So I believe the problem is mostly because of your first point. $\endgroup$
    – Tita
    Dec 30, 2022 at 17:04
  • 1
    $\begingroup$ I edited my answer to show one way around the use of an "if" statement. $\endgroup$
    – prubin
    Dec 30, 2022 at 18:59
  • $\begingroup$ Thank you for your suggestion! I am unsure how I could do that in Excel, but I'll try and come back in case of a question. Also, in the last constraint I don't undestand where k should go, like let's say I'm calculating for week 5, then $k=5-t_i+1$ until $5$ and $x_{ij}$ changes how? $\endgroup$
    – Tita
    Jan 1, 2023 at 12:13
  • $\begingroup$ Also, what happens if I'm trying to find the constraint for $Y_{11}$? Then $k=1-3+1=-1$, what does that mean? $\endgroup$
    – Tita
    Jan 1, 2023 at 12:28
  • 1
    $\begingroup$ You're welcome. $\endgroup$
    – prubin
    Jan 3, 2023 at 2:53
2
$\begingroup$

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 enter image description here

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

  • Second enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your input. May I ask what software you used to make your answer? The original management I'm trying to make has about 14 projects in 24 weeks and as you said there'll be many overlaps. I am not limited to use Excel, so I would love to try what you have used as well! $\endgroup$
    – Tita
    Jan 1, 2023 at 12:03
  • $\begingroup$ @Tita, your welcome. For the first, I used MSproject. I know already there are many open-source software with the same ability. For the second I have used GAMS. You can use many others you want with your favorite AML/GPL. $\endgroup$
    – A.Omidi
    Jan 1, 2023 at 12:11
2
$\begingroup$

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 enter image description here enter image description here

$\endgroup$
17
  • $\begingroup$ Thank you for your answer. Okay, so like I mentioned in the OP, $z=max W_j$. I don't quite understand what the first constraint you're suggesting is, that the sum of the days that a project runs for is equal to the time it needs? How did you get the second constraint? Also, are you suggesting that the changing variables are the $Y_{ij}$ instead of $x_i$? I am looking to understand the problem here :/ $\endgroup$
    – Tita
    Dec 30, 2022 at 18:08
  • $\begingroup$ Also, I don't understand how I am supposed to add the second suggested constraint to Solver or in Excel's cells for that matter. Can you please elaborate your answer? $\endgroup$
    – Tita
    Dec 30, 2022 at 18:11
  • $\begingroup$ Your Y's are in matrix type, companies along the rows, weeks across columns. So select from week 2 to 9(ending week) and add sum constraint for all companies or projects. $\endgroup$ Dec 30, 2022 at 18:21
  • $\begingroup$ 2nd constraint ensures workers once assigned to a project remain there through the project duration which means Y's for a company will be either like 1,1,0 or 0,0,1 or 1,0,0 or 0,0,1, 0,1,0 but never like 1,0,1 because that implies workers from that project are off for the week in the middle. But you don't want that. $\endgroup$ Dec 30, 2022 at 18:25
  • 1
    $\begingroup$ LP Simplex is solving it $\endgroup$ Jan 2, 2023 at 19:42
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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