Sequencing to Minimize Tardy Tasks, Sequencing to Minimize Tardy Task Weight

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.

Leave a Reply

Your email address will not be published. Required fields are marked *