Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Sequencing and Single-Machine Scheduling
verfasst von : David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker
Erschienen in: Decision Diagrams for Optimization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this chapter we provide an in-depth study of representing and handling single-machine scheduling and sequencing problems with decision diagrams. We provide exact and relaxed MDD representations, together with MDD filtering algorithms for various side constraints, including time windows, precedence constraints, and sequence-dependent setup times. We extend a constraint-based scheduling solver with these techniques, and provide an experimental evaluation for a wide range of problems, including the traveling salesman problem with time windows, the sequential ordering problem, and minimum-tardiness sequencing problems. The results demonstrate that MDD propagation can improve a state-of-the-art constraint based scheduler by orders of magnitude in terms of solving time.