Solving a combined cutting-stock and lot-sizing problem with a column generating procedure (Q2482385)

This paper considers a combined cutting-stock (trim loss) and lot-sizing problem for which a concave minimization problem is derived. The authors suggest a new column generating procedure which includes characteristics of two existing procedures from the literature: a tree-search heuristic given by the authors [Eur. J. Oper. Res. 120, No. 2, 327--342 (2000; Zbl 0946.91021)], which works well for small-size problems, and a sequential heuristic by \textit{R. W. Haessler} [Manage. Sci., Appl. 17, B793--B802 (1971)], which works well for large-size problems. Numerical results are provided which indicate that the new heuristic performs better on average than the two existing algorithms. Then a generalized cutting-stock problem is considered in which only a setup cost is incurred for each pattern change. For this case, the new heuristic is compared to four solution procedures from the literature and it turned out that it also works well for the generalized problem.