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” b_{i} of how many resources are available at any time and each task t has a requirement r_{i}(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 m_{k}(i) to be the number of triples in S that have i in their kth value. So m_{2}(4) is the number of triples with a 4 in position 2. Notice that for a legal matching to be possible, m_{k}(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.
- X
_{0}, Y_{o}and Z_{0}tasks for each element in q (the number of elements in T) - X
_{ij}tasks where i runs from 1 to q and j runs from 1 to m_{1}(i). - Similar Y
_{ij}(using m_{2}(i)) and Z_{ij}(using m_{3}(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 X
_{0} - A Y or Y
_{0} - A Z or Z
_{0} - An F or G

The X_{0}/Y_{0}/Z_{0} 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.

If ALL resources should be allocated at ALL times, then we can see the case of 3 processors and 3 resources as the vertex cover of a 3-colorable graphs with max deg. 3 (which can be easily created from a refined 3-sat instance). Of course, we need to use the fractional numbers then we take common divisor.

For 3 processor 1 resource, some novel idea is needed.

Th. Ng.

Oh, it is a reduction from 3-partition problem that solves the 3 processors 1 resource case once for all.

https://en.wikipedia.org/wiki/3-partition_problem

Notice the claim: “The 3-partition problem remains NP-complete when every integer in S is strictly between B/4 and B/2”

Safe to omit my previous post.

Nice weekend,

Th. Ng.

What G&J do in the paper is show how in general you can take a k processor j resource problem and turn it into a k processor 1 resource problem, and similar things like that. But I’m glad to hear there’s a 3-partition way. Hopefully it’s easier 🙂

GJ1975 reduces 3DM to 3-partition problem. And 3-partition problem (with tight bounds on values of items in the (multi-)set) can be seen as special case of the 3 processors 1 resource scheduling.