I spend a bit of time trying to see if there was an easy reduction between this problem and one of the other scheduling ones, but I couldn’t find anything. So we’ll do it the hard way.
The problem: Given a set T of tasks, each with a length of 1, a set of m processors, and set of r resources. Each resource i has a “bound” bi of how many resources are available at any time and each task t has a requirement ri(t) denoting how many of resource i it needs. We’re also given a deadline D.
Can we find an m-processor schedule for all tasks that:
1) Meets the deadline, and
2) For all time units, ensures that all of the processors running in that time unit do not exceed the resource bounds for any resource?
Example: Suppose I have 4 tasks and 1 resource:
- Task 1 uses 2 units of the resource
- Task 2 uses 3 units of the resource
- Task 3 uses 4 units of the resource
- Task 4 uses 5 units of the resource
If there are 5 units of the resource available, we can get this task done in 3 time steps (Task 4, then 1 and 2, then 3)
If there are 7 units available, we can get the task done in 2 time steps (1 and 4, then 2 and 3)
If there are 14 units available, we can do everything in one time step.
Reduction: The paper by Garey and Johnson proves several variants of the problem, The one I’ll do is in Lemma 3.4, which has 5 processors and 8 resources. They go on from there to show the variant with 3 processors and 1 resource is also NP-Complete, but we only care about the general problem.
The reduction is from 3DM, In this case, we’re assuming that W, X, and Y (the 3 sets in the 3DM problem) are all the same set T, and S is our set of triples from T. Define a value mk(i) to be the number of triples in S that have i in their kth value. So m2(4) is the number of triples with a 4 in position 2. Notice that for a legal matching to be possible, mk(i) has to always be at least 1.
So we build an instance of the resource constrained scheduling problem with 5 processors and 8 types of resources. The tasks are:
- One “S” task for each triple in S.
- X0, Yo and Z0 tasks for each element in q (the number of elements in T)
- Xij tasks where i runs from 1 to q and j runs from 1 to m1(i).
- Similar Yij (using m2(i)) and Zij (using m3(i)) tasks.
- “F” tasks from 1 to q.
- |S|-q “G” tasks.
The deadline is |S|.
The resource requirements are set up so that during each time unit, we have 5 processors running:
- An S task
- An X or X0
- A Y or Y0
- A Z or Z0
- An F or G
The X0/Y0/Z0 tasks all correspond to an element in T, and can only be run along with an F and the S task that is the triple of the X, Y, and Z elements in S. The F task makes sure that we have chosen a legal matching. The matching consists of the S triples chosen along with an F task. (The G tasks are there to fill the rest of the timesteps) .
Difficulty: 7. More if you keep going and refine the problem down to 3 processors and 1 resource.