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