Mathematical modeling and optimal blank generation in glass manufacturing (Q2336874)

Summary: This paper discusses the stock size selection problem [\textit{M. L. Chambers} and \textit{R. G. Dyson}, ``The cutting stock problem in the flat glass industry-selection of stock sizes'', Oper. Res. Quart. 27, No. 4, 949--957 (1976; \url{doi:10.1057/jors.1976.187})], which is of relevance in the float glass industry. Given a fixed integer \(N\), generally between 2 and 6 (but potentially larger), we find the \(N\) best sizes for intermediate stock from which to cut a roster of orders. An objective function is formulated with the purpose of minimizing wastage, and the problem is phrased as a combinatorial optimization problem involving the selection of columns of a cost matrix. Some bounds and heuristics are developed, and two exact algorithms (depth-first search and branch-and-bound) are applied to the problem, as well as one approximate algorithm (NOMAD). It is found that wastage reduces dramatically as \(N\) increases, but this trend becomes less pronounced for larger values of \(N\) (beyond 6 or 7). For typical values of \(N\), branch-and-bound is able to find the exact solution within a reasonable amount of time.