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:
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.