How to split set of dependent steps into groups

Question

I have a set of steps to perform, each with a time (in minutes).

I also have a set of dependencies (ie, step 7 must come after step 5).

Assuming no loops, what's the correct algorithm for grouping them into groups, where each group has a total time less than a certain amount.

Obviously, unless the dependencies give a linear order, there are various ways of arranging the steps, is it easy/possible to work out the most optimal (ie, requires the fewest groups).

Currently my steps and dependencies are in SQL, but I'd happily have a solution in another language.

Answer 1

When there are no dependencies, this is the NP-hard bin packing problem. Bin packing has some clever exact algorithms, but I'm not sure how to adapt them, and they're hard to implement anyway. Here's an analog of the pretty good First Fit Decreasing approximation (11/9 asymptotic approximation ratio for the original; no idea if the new version is any good).

First dump all of the tasks and their dependencies out of your database. Topologically sort the tasks using a variant of Kahn's algorithm where, among all of the tasks whose dependencies all have been chosen previously, choose the longest to be next. Schedule this task in the first group where it both fits and does not precede a dependency.