Tag Archives: Subset Sum

Sequencing With Deadlines and Setup Times

Is it weird that G&J call these problems “sequencing” and not “scheduling”?  They use “scheduling” for multiprocessor problems, and shop scheduling problems.  I guess the thinking is that single-processor problems are just “sequences” of what you put on the processor.

The problem: Sequencing with Deadlines and Setup Times.  This is problem SS6 in the appendix.

The description: We’re given a set of T tasks, each task with a length l(t) and deadline d(t).  We also have a set of “compilers”, C, and each task has a specific compiler k(t).  Each compiler has a setup time l(c).  Can we find a one-processor schedule for T that meets the deadlines of all tasks with the additional constraint that if two tasks are scheduled with different compilers, we must pay the setup cost of the second task’s compiler before starting the second task?

Example: I’m not sure “compiler” is the best word for C.  I think of it as more of a preprocessor (and in fact, the paper by Bruno and Downey that has the reduction calls it a “setup task”).  Each task needs some preprocessing to be done before it can run, and if you run two tasks that need the same preprocessing in a row, you can do them both one after the other. Otherwise, you need the preprocessing to happen (immediately) before you start the task.

So, suppose I have 2 compilers:

Compiler Setup time
1 5
2 7

And 4 tasks:

Task Length Deadline Compiler
1 5 10 1
2 3 20 2
3 3 23 2
4 10 100 1

..Then if we schedule task 1 first, its setup + length gets it done at time 10.  Then we do the setup for task 2, so it finishes at time 20.  Task 3 uses the same “compiler”, so does not need to do setup time, so will finish at time 23.  Task 4 uses a different compiler, so needs to re-run compiler 1’s setup time of 5, and will be done at time 38.

Notice that the most “efficient” schedule that minimizes the number of setups we have to do will not schedule all tasks by their deadlines.

Reduction: I’m pretty sure this problem is Theorem 1 in the paper by Bruno and Downey.  They say they reduce from Knapsack, but since there aren’t any weights, they’re really using Sum of Subsets.  The original set S has N elements, a target B, and the sum of all elements in the set is called t0 (which will, of course, be > B).  There will be N+2 “classes” of 3 tasks each that share the same setup task.  The setup for all classes Ci takes time 1 and has 3 tasks: one that takes time 1, one that takes time si (the corresponding element in S), and a third task that takes time H*si, where H is the larger of t0 and N+2.  The 2 “extra” classes Co and Cn+1 work similarly, but use t0 instead of si.  The deadline for the first task in all classes is d1 = 2(N+2) + B.  The deadline for the second task in all classes is d2 = 3N+5+3t0+2Ht0-HB.  The deadline for the third task in all classes is d3=3N+5+3t0+3Ht0.

They go on to show the following facts:

  • In a feasible schedule, you can’t have a d3 task finish before the d1 deadline (there is no time for it).
  • In a feasible schedule, you can’t finish the second task of C0 or Cn+1 before d1.  (Since the second task takes t0 time, feasibly scheduling everyone’s first tasks with their setup times does not leave enough time left).
  • In a feasible schedule, we can only setup 2N+3 setup tasks at most. (More leaves too much time for setup and processing and someone will miss their d3 deadline).
  • In a feasible schedule, there is exactly one task that gets setup once (that is, it gets set up, and does its three tasks in sequence).  This is because of the first bullet and the fact that we have a limit of setup tasks.
  • In a feasible schedule, you never do the first task then the third task without doing the second task  (You can rearrange other feasible schedules to have this property and remain feasible).

What results from these facts is that a feasible schedule has: a bunch of first tasks (preceded by the setup task), a bunch of first and second tasks in sequence (preceded by the setup task), and a single class that does its setup then all three tasks.  This last sequence crosses over the d1 deadline.  Then we need to set up and schedule the second and third tasks of all of the classes we only did the first task for before the d2 deadline.  Then we will set up and schedule the last task of all classes that have a third task remaining.

It turns out that the classes we chose to do the first 2 tasks before the d1 deadline for have costs (and second task length) of exactly B.

Difficulty: 7.  This is a really good paper that does a really good job of proving each of the above facts along the way and showing how it all works (many other papers would resort to saying some of these proofs were “obvious”, which I don’t think they are).  Having said that, I don’t know how anyone comes up with these classes- especially the deadlines- without weeks of trial and error, and that is too much for a student to manage on their own.


It’s kind of amazing that I’ve gotten this far without needing such a classic problem.  But I was writing up the next post and needed to link to my Knapsack article, and it wasn’t there, so..

The problem: Knapsack.  (More technically, “0/1 Knapsack”).  This is problem MP9 in the appendix.

The description: Given a set U of items, each item u in U has a profit p(u), and a weight w(u).  (G&J call these “value” and “size”), and positive integers B and K.  Can we create a subset U’ of U that has total profit at least K, but total weight at most B?

Example: Knapsack is one of my all-time favorite problems, which probably says something about me.  But I inflict it on my students at all levels of the curriculum – it’s a good motivation to introduce parallel arrays, and building simple classes at the low levels, the fractional version is a good example of a greedy algorithm, and the 0/1 version is a good example of where greedy fails.  It also fascinates me how it’s an example of a problem where a problem that has infinite solutions (Fractional Knapsack, when you can take any proportion of an item) is easily solvable, but a problem that has fewer solutions to consider (0/1 Knapsack, where there are “just” 2 choices for each item) is intractable.

Anyway, here is my classic “Your Greedy Approach Won’t Work” example:

Item Profit Weight
1 5 4
2 3 3
3 3 3

If B=6, the best option is to choose items 2 and 3.  But greedily picking items by profit/weight ratio (which works for the Fractional Knapsack problem) will choose item 1, and lose profit.

Reduction: G&J reference Karp’s paper and this is a classic reduction you see in most books that do this problem.  You go from Subset Sum.  We’re given a set S, and an integer K.  We create a set U with the same number of elements, make the profit and weight of each element the same, and equal to the size of the corresponding element in S.  We set K’=B=K.

If the original set had a subset summing to K, then taking those elements will make us a profit of K’ and a weight of B.

If we have a Knapsack solution with profit K’ or more, then since the profits of all items are equal to their weights, the only for the total weight to not exceed B is for the profit to be exactly K’.  So taking the corresponding items in S will get a sum equal to exactly K.

Difficulty: 3.  I use this as an easy homework or test question all the time.

Protected: K-Vertex Cover

This content is password protected. To view it please enter your password below:

Protected: Subset Product

This content is password protected. To view it please enter your password below: