Precedence Constrained Scheduling

SS8 is “Multiprocessor Scheduling”, which is done in Section 3.2.1

Here’s SS9, which uses the non-book problem from last week.

The problem: Precedence Constrained Scheduling.  This is problem SS9 in the appendix.

The description: Given a set T of tasks arranged in a partial order, each of length 1, a set of m processors, and a positive deadline D.  Can we schedule the tasks in T in a way that obeys the precedence constraints and finishes by deadline D?


Suppose we had the following simple precedence graph:

With 2 processors, the earliest feasible schedule will finish at time 3 (timestep 1 schedules 2 of a,c, and d, timestep 2 schedules the remaining one, and then we can finally schedule b after that).  With 3 processors, we can finish at time 2 (schedule all of a,c, and d in timestep 1, then b right afterward).

Reduction: This is problem P2 in the paper by Ullman and the reduction uses the “Single Execution Time with Variable Number of Processors” problem from last week.  The main difference between that problem and this one is that instead of having a varying number of slots at each time, now we have K processors for all time steps.

So we start with an instance of the variable processor problem and add a bunch of new jobs Iij where i runs through each time step, and j runs from 0 to n – ci. (n is the number of jobs, ci is the number of processors available at time i).  The precedence graph keeps all of the old precedences and also has Iij come before Ii+1,k  for all j and k.  (So all I jobs at time i come before all I jobs at time i+1).  We have n+1 processors and the same deadline.  The idea is that the extra I jobs all have to run at their specific timestep, and they “fill” the empty processor slots between the ci processors available in the original and the n+1 processor slots available in this version of the problem.

Difficulty: 4, mainly because the variable # of processors problem we’re reducing from is hard to understand.  But this is a classic “go from a variable number of things to a larger fixed number of things” technique that can be used for lots of problems.


Leave a Reply

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