On the complexity of dynamic programming for sequencing problems with precedence constraints

Dynamic programming has been successfully used in the past to solve a large class of precedence constrained sequencing problems including for example, the assembly line balancing problem and the total tardiness problem on a single machine. The main limitation of this method has been the amount of storage required, which is directly related to the number of ideals in the precedence structure. The paper presents classes for which this number can be efficiently computed, enabling a decision to be made, in advance, whether the storage requirements of dynamic programming would be excessive for the problem. It develops regression equations based on large-scale computational experiments, which lead to surprisingly good approximations for the number of ideals. The paper also reports on a computational study, comparing the relative effectiveness of various implementations of dynamic programming. A common theme throughout the paper is that the width of the precedence constraints plays the most important role in determining th storage requirements of dynamic programming for a sequencing problem.