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.

In the figure, the tasks are called a,b,c,d, but in the text they are called by numbers.

For example, the sentence: “A two-processor preemptive schedule could be something like: P1: (1,1,1,2,2,4) and P2: (4,4,4,3,3,3), getting both tasks done at time6”

should be: “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 all tasks done at time 6.”

Thanks for catching that- I fixed it