Return to search

Empirical Evaluation of Construction Methods for Relaxed Decision Diagrams in Scheduling / Empirisk Utvärdering av Konstruktionsmetoder för Relaxerade Beslutsdiagram inom Schemaläggning

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.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-196223
Date January 2023
CreatorsBerntsson, Dennis
PublisherLinköpings universitet, Programvara och system
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0014 seconds