Empirical Evaluation of Construction Methods for Relaxed Decision Diagrams in Scheduling

Abstract: Decision diagrams have recently emerged as a promising approach for difficult scheduling problems, along with other challenging discrete optimization problems. Decision diagrams can offer a compact representation of the solution space, and has the ability to capture complex constraints that are hard to model or express in other techniques. This thesis explores two standard construction methods for relaxed decision diagrams, top-down construction and incremental refinement. The techniques are compared on their ability to handle scheduling problems with multiple time windows and precedence constraints. The construction methods are evaluated on several metrics, including generated bound, execution time, and the size of the diagram, on instances of the problem with up to 200 tasks. The results show that incremental refinement generates smaller diagrams with good bounds when compared to the top-down compilation algorithm; the reduction in diagram size and increase in bounds for incremental refinement comes at the expense of execution time compared to top-down compilation.