3
$\begingroup$

I have a challenge that is a bit backwards from the usual labour resource leveling problem.

In my case I have a fixed budget pool over a period to deliver some of the work packages (not enough per period to deliver all). So I need to look at how to efficiently assign work packages to the period while keeping in mind the dependencies.

Thinking this through it's probably an knapsack problem with each period's budget being a bucket to be filled - so this, potentially, is more of an excel solution than a project software one - even though I face this kind of problem any time an organisation is attempting to run a program without a specific allocated budget (typical for government where applying for a budget is often artificially hard).

I'm not an OR person so this is a bit vague for me :)

EDIT: Work packages can have funds allocated against their start, even if they flow over more than one period so we can consider their start date to be the date they are fully funded and forget about them after this.

Dependencies are precedence constraints

Work packages can start in any time period as long as their dependencies are met but I would like to maximise the work done in a period.

Improve this question
$\endgroup$
7
  • $\begingroup$ You will need a binary variable $x_{i,t}$ if work package $i$ is assigned to period $t$ with budget constraints, assignment constraints (one period per work package ?), and dependency constraints. Could you elaborate on the dependencies ? Are they precedence constraints ? $\endgroup$
    – Kuifje
    May 17, 2022 at 8:22
  • $\begingroup$ Can a work package start at any period, or only at a single given period? $\endgroup$
    – fontanf
    May 17, 2022 at 8:51
  • $\begingroup$ the work package can start in any period as long as its own dependencies are met, but it might be a dependency for other work packages. $\endgroup$
    – baradhili
    May 17, 2022 at 10:11
  • $\begingroup$ From what I understand, the part of the budget which has not been allocated at one period adds up to the budget of the next period. Is that right? $\endgroup$
    – fontanf
    May 17, 2022 at 12:20
  • 1
    $\begingroup$ Then I don't understand the "EDIT" paragraph $\endgroup$
    – fontanf
    May 17, 2022 at 13:21

1 Answer 1

Reset to default
3
$\begingroup$

Define a binary variable $x_{it}$ that takes value $1$ if and only if work package $i$ is assigned to period $t$ (i.e., work package starts at time period $t$).

If there is a cost $c_{it}$ per couple $(i,t)$, you can minimize the objective function $$ \sum_{i,t} c_{it}x_{it} \tag{1} $$ subject to

  • One period per work package: $$ \sum_{t} x_{it} = 1 \quad \forall i \tag{2} $$
  • Budget constraints: $$ \sum_{i,t} c_{it} x_{it} \le \mbox{Budget} \tag{3} $$
  • Precedence constraints: for each work package $i$, let $p(i)$ be the set of work packages that must be done before $i$ $$ x_{it} \le \sum_{h\in\{1,..., t-1\}} x_{jh} \quad \forall i, \forall j \in p(i) \tag{4} $$

If you do not have enough budget for all work packages, you can maximize $\sum_{i,t}x_{i,t}$ and replace constraints $(2)$ with $\sum_{t} x_{it} \le 1$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I think that the last constraint should take into account that a work package can last more than one period $\endgroup$
    – fontanf
    May 17, 2022 at 10:20
  • $\begingroup$ good point. I think OP should elaborate on the nature of the dependecies, as right now it is unclear. $\endgroup$
    – Kuifje
    May 17, 2022 at 10:40
  • $\begingroup$ the dependencies are only other tasks. There are no resource dependencies $\endgroup$
    – baradhili
    May 17, 2022 at 12:09
  • $\begingroup$ @Kuifje I think I get it.. the last sentence is something like a controlled annealing step? Now how to do this in R or Python... $\endgroup$
    – baradhili
    May 17, 2022 at 14:01
  • $\begingroup$ This is a pure integer program, which you can solve in Python with pulp or pyomo. $\endgroup$
    – Kuifje
    May 17, 2022 at 14:27

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.