# Project task scheduling based on available budget per period

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.

• 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 ? May 17 at 8:22
• Can a work package start at any period, or only at a single given period? May 17 at 8:51
• 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. May 17 at 10:11
• 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? May 17 at 12:20
• Then I don't understand the "EDIT" paragraph May 17 at 13:21

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$$.

• I think that the last constraint should take into account that a work package can last more than one period May 17 at 10:20
• good point. I think OP should elaborate on the nature of the dependecies, as right now it is unclear. May 17 at 10:40
• the dependencies are only other tasks. There are no resource dependencies May 17 at 12:09
• @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... May 17 at 14:01
• This is a pure integer program, which you can solve in Python with pulp or pyomo. May 17 at 14:27