Resource Constrained Scheduling

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:

  1. An S task
  2. An X or X0
  3. A Y or Y0
  4. A Z or Z0
  5. 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.

4 responses to “Resource Constrained Scheduling

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

  2. Oh, it is a reduction from 3-partition problem that solves the 3 processors 1 resource case once for all.
    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.

  3. 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 🙂

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

Leave a Reply

Your email address will not be published. Required fields are marked *