Optimal Sequencing by Modular Decomposition: Polynomial Algorithms

We show that the combination of dynamic programming with partial-order decomposition algorithms enables us to solve sequencing problems in polynomial time for substantially larger classes of precedence constraints than previously realized. The algorithm's efficiency depends on the maximum number of jobs that are not related by the precedence constraints in certain subsets of the jobs. We also demonstrate how to modify this general algorithm lo take advantage of special problem characteristics.