Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Bergman, D., Cire, A.A., van Hoeve, WJ., Hooker, J. (2016). Sequencing and Single-Machine Scheduling. In: Decision Diagrams for Optimization. Artificial Intelligence: Foundations, Theory, and Algorithms. Springer, Cham. https://doi.org/10.1007/978-3-319-42849-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-42849-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-42847-5
Online ISBN: 978-3-319-42849-9
eBook Packages: Computer ScienceComputer Science (R0)