I may have missed something obvious but I really don't know how to tackle the problem of generating various orderings. Any advice, please?
For any significant-sized input the number of orderings will be too large to do anything useful with. For an input small enough that the set of feasible orderings will fit in memory I would simply generate all permutations and screen for feasibility rather than attempting to create an enumeration algorithm. Create a comparability matrix and use it to prune the permutation tree, perhaps? N^2 bits doesn't sound prohibitive. This has probably been studied but I'm at work so I'll speculate. For larger inputs with many constraints it may be worthwhile to create an enumeration algorithm. For purposes of empirical testing of build-ordering systems it might be sufficient to go into the algorithm and randomize the selection processes whenever it makes arbitrary choices. This may or may not be easily achieved by randomly pre-sorting the input, depending on the internals of the algorithm. If the sort is stable that will work. An efficient feasible ordering enumerator for arbitrary finite partial ordered sets would have to have a recursive structure because there can be arbitrarily complex subgraphs with mutually incomparable nodes, nested to arbitrary depth. Another point regarding applications: if you are interested in testing build orders (as I very much am, that's what I'm doing manually right now) you can't just convert the partial order to a total order arbitrarily because modern build systems exploit incomparables in the partial order to parallelize build steps. If you impose an arbitrary order on the incomparables you serialize the build artificially, which prevents testing for parallel-step interaction. If there is enough interest to justify adding an efficient deterministic enumerator for poset orders I'll write one. Graph-theoretical algorithms are a fun way to spend the weekend :-)