This is one of those reductions that is easy because you remove everything that makes the problem hard. It always feels like cheating to do this, but I guess it shows that adding extra complexity to a hard problem will never make it easier..
The problem: Preemptive Scheduling. This is problem SS12 in the appendix.
The description: Given a set T of tasks arranged in a partial order, each task t has a positive length l(t). We have a set of m processors and an overall deadline D. Can we create a preemptive schedule for T that obeys the precedence constraints and meets the overall deadline? A preemptive schedule allows tasks to be partially run on a processor and then removed, and we can finish it at some later time.
Example: Here is a simple partial order:
The number of the task is its length. So task a takes 3 time units, for example.
A two-processor preemptive schedule could be something like: P1: (a,a,a,b,b,d) and P2: (d,d,d,c,c,c), getting both tasks done at time6.
If we did not allow preemption, we would not be able to fit task d along with task a, so we couldn’t do anything on P2 while P1 was running task 1.
Reduction: The paper by Ullman which we used for Precedence Constrained Scheduling has the reduction. He basically notes that Precedence Constrained Scheduling is a special instance of Preemptive Scheduling where all lengths of all jobs are 1. In that case, no preemption is possible. So the reduction is basically “use the exact same problem”.
Difficulty: 2. I usually reserve Difficulty 1 for “this is the same problem”, but here, there is a little bit of insight to convince yourself that you can interpret the problem this way.