How to break a set of dependent steps into groups
I have a set of steps to follow, each with time (in minutes).
I also have a set of dependencies (i.e. step 7 should appear after step 5).
Assuming no cycles, what's the correct algorithm to group them into groups where each group has a total time less than a certain amount.
Obviously, if the dependencies do not lead to a linear order, there are various ways of organizing the stages, is it easy / possible to work out the most optimal ones (i.e., fewer groups are required).
Currently my steps and dependencies are in SQL, but I would love to find a solution in another language.
source to share
If there are no dependencies, it is a NP-hard bin packaging issue. Bean packing has some clever exact algorithms, but I'm not sure how to adapt them and they are difficult to implement anyway. Here is an analogue of a good approximation of the first approximation (11/9 asymptotic approximation for the original, no idea if the new version is good).
First, remove all tasks and their dependencies from your database. Sort tasks topologically using a variant of the Kahn algorithm , where among all tasks whose dependencies have all been selected previously, choose the longest to be next. Schedule this task in the first group where it fits and does not precede dependencies.
source to share