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: (1,1,1,2,2,4) and P2: (4,4,4,3,3,3), getting both tasks done at time6.

If we did not allow preemption, we would not be able to fit task 4 along with task 1, 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.