# How to prove that this problem is NP-complete (or NP-Hard) I have the following data:

• A set $$V$$ of tasks, the starting time $$s_j$$ of each task and the duration $$p_j$$ of each task.

• A set $$K$$ of resource, each resource has an availability function $$R_{k}$$ that is piecewise constant.That is, for each $$t = 0, .., T-1$$, we precise $$R_{k}(t)$$ the number of units available at $$t$$. $$R_k$$ is an array of length $$T$$.

• Each task $$j$$ needs $$r_{j,k}$$ resources to be processed (it could be zero). This quantity needs to be available during all the processing time starting from $$s_j$$.

For example consider :

• Task$$A$$ has processing time $$3$$ and starts at time period $$t=2$$ and needs 2 units of some resource $$k$$
• Task $$B$$ has processing time $$4$$ starts at time $$t=3$$ and needs 3 units of the same resource $$k$$.

Then if $$R_{k}(t) = [*,*,2,6,6,3,*,*]$$ then we are ok since at time $$t=2$$ only task $$A$$ is active and it requires $$2$$ units, at time $$t=3$$, both tasks are active and the sum of their utilization is $$2+3 = 5 \leq 6$$; same at time $$t=4$$. At time $$t=4$$, only task $$B$$ is active and it requires $$3$$ units.

However, if $$R_{k}(t) = [*,*,2,4,6,3,*,*]$$, is not ok since at time $$t=3$$, both tasks $$A$$ and $$B$$ are active and their total use is equal to $$5$$ wheras only $$4$$ units are available.

Here is my attempt to verify that the resource utilization at each $$t$$ is no larger than the availability function. So the answer is yes or no (we can say that this is a decision problem).

For each time t in [0,T-1]   For each resource k in K      total_use = 0, active_set = A     for each task j in V       if s_j<=t and s_j+p_j > t and r_{j,k}>0 \if the task is active at time t and it requires positive amount of resource k in order to be processed)         total_use += r_{j,k}         active_set := active_set U {j}        if total_use > R_{k}(t)         print(at time t the usage of resource k exceeds its capacity, active_set)         return False return True 

The algorithm here is pseud-polynomial. Unfortunately, I need to find a polynomial one in order to say that the problem is in $$\mathcal{NP}$$. 