I don’t want to constantly restate reductions that are done in the G&J book, so I’ll just state that problem SS2, “Sequencing to Minimize Tardy Tasks” is done in G&J on page 73.

The next problem has a very similar title, but is a pretty different problem:

**The problem: **Sequencing to Minimize Tardy Task Weight. This is problem SS3 in the appendix.

**The description: **Given a set T of tasks, each with a length, a deadline, and a weight (think “penalty”), and an integer K, can we find a one-processor schedule for T such that the sum of the weights of the tasks that are not completed before their deadline is K or less?

**Example: **Here’s a pretty simple example to show what the hard decision is:

Task | Length | Deadline | Weight |

1 | 1 | 1 | 3 |

2 | 2 | 3 | 4 |

3 | 3 | 3 | 5 |

Obviously, we can only do either task 3, or both of task 1 and 2. The current weights favor doing tasks 1 and 2 (because we want to make the weights of missed tasks small), but changing the weight values can change the decision.

**Reduction: **This is done in Karp’s paper. We reduce from Partition. Let S be the set we are trying to Partition. We’ll have a task for each element in the S. The length of each task and its weight will be equal to the size of the element in S. K = half of the sum of all of the elements in S. The deadline for all tasks is also K.

Notice that the only way to get total weight K (or less) after the deadline is to get total length K (or more) done before the deadline. We can’t do *more* than K length before the deadline (since the deadline is K). So the only way to have a feasible schedule is to have a set of tasks whose lengths are exactly K, which is a partition.

**Difficulty**: 3. I think this is a little easier than last week’s since you don’t have to make up that boundary task in the middle. Still, going from one set of things (the elements in S) to 3 values (length, deadline, and weight) gives opportunities for confusion.