Dynamic Programming to Minimize the Maximum Number of Open Stacks
Maria Garcia de la Banda, Peter J. Stuckey
INFORMS Journal on Computing · 2007 · Volume 19 · Issue 4
Abstract
We give a dynamic-programming solution to the problem of minimizing the maximum number of open stacks. Starting from a call-based dynamic program, we show a number of ways to improve the dynamic-programming search, preprocess the problem to simplify it, and determine lower and upper bounds. We then explore a number of search strategies for reducing the search space. The final dynamic-programming solution is, we believe, highly effective.
Keywords
dynamic programming, minimization of maximum number of open stacks, cutting sequencing
Enable JavaScript for citation tools and additional paper interactions.