Scheduling with Individual Deadlines

I feel like this problem is an easy extension of a problem we’ve already done.  This worries me, because why would it show up as a separate problem with a separate reference in G&J if that is the case?

The problem: Scheduling with individual deadlines.  This is problem SS11 in the appendix.

Description: Given a set T of tasks, each of length 1, arranged in a partial order, a set of m processors, and a deadline d(t) for each task t, can we schedule all tasks to meet all deadlines?

Example: Here’s a precedence graph:

Suppose the deadlines are:

Task Deadline
1 1
2 3
3 2
4 1
5 2
6 3

If we have 2 processors, then we can schedule all tasks by doing each task exactly as its deadline is coming up.  If we add one more requirement in the partial order from 3 to 5, then these tasks cannot all be finished by the deadline.

Reduction (easy version): When I read this problem, it seemed very similar to Precedence Constrained Scheduling.  The difference is that in that problem, we’re given a single deadline D that all tasks must be completed by, but in this problem, each task can have its own deadline.

But this still leads to a pretty easy reduction from PCS: We take our PCS instance, use the exact same tasks, use the same number of processors, and make each task’s individual deadline be D.  So our Individual Deadline instance is feasible exactly when all tasks are finished by time D.

This feels too easy.  Maybe I’m misreading one of the problems.  So, to be safe..

Reduction (Brucker, Garey, and Johnson version):

The reduction in the paper goes from Vertex Cover.  So we’re given an undirected graph G=(V,E), and a K.  Define define v = |V|, e= |E|, a= v+ e(e+1).  Define m = a + e+ v.  This will be the number of processors.  Define D = 3e+3.  This is the largest deadline for any task.

There will be m*(D-1)+1 tasks. Task T0 has deadline 1.  There will be many other “dummy” tasks Tij that are set up so that they have to start at time j and have to end at time j+1.  This is enforced by having each Ti,j have to come before Ti,j+1 in the partial order.  The number of i tasks at each j changes:

  • Ti,1 where i goes from 1 to m-k
  • Ti,2, where i goes from 1 to m-e
  • Ti, 2+j for each j from 1 to e, where i goes from 1 to v+j
  • Ti, e+2+j, for each j from 1 to e, where i goes from 1 to a+v+j-1
  • Ti, 2e+2+j, for each j from 1 to e, where i goes from 1 to e+v

T0 is the root of all of these and comes before each Ti,1.

Then we add the “graph-dependent” tasks.  Each vertex vi has a task that has to come after T0 and has deadline e+3.  Each edge ej spawns two chains of j tasks (E’j(1) through E’j(j) and E”j(1) through E”j(j))  each, all of which have deadline 2e+3.  We’ll also have two other groups of tasks for each edge: L’j(1) through L’j(a) and L”j(1) through L”j(a). The last E’ task for each j comes before all of the corresponding L’ tasks, and the last E” task for each j comes before all of the corresponding L” tasks.  Each of these L tasks has a deadline D-j+1.

Edges in G also create precedence constraints.  The edge ej= (vq, vr), with q < r, creates the ordering vq->E’j(1) and vr->E”j(1).

If G has a Vertex Cover, then that means that each edge in E has at least one endpoint in the cover.  The jobs for these vertices will be scheduled at time 1.  Since the vertex jobs have to be run before the corresponding edge jobs, we can run the E’ or E” job that was set by the last precedence constraints above at time 2.  Once that chain finishes, we can run the L jobs.

If we have a valid schedule that meets all deadlines, we must have scheduled T0 first, and each Ti,j at time j. This means we only have so many slots to schedule the E chains.  Since vertex tasks have to happen before these chains, we need to schedule k vertex tasks at time 1.  If the schedule is feasible, that must be a cover. (Because if it wasn’t, then there is an edge that does not have it’s E’ or E” chain start at time 2, which is too slow).

Difficulty: The easy way is a 2.  The way from the paper is an 8, because it’s hard to see why the specific numbers of dummy tasks comes from, why you need 2 chains (E’ and E”.  You need them because you don’t know which endpoint of the edge will be in the cover), why you need the L tasks, and so on.

Leave a Reply

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