Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction

A sequential grouping heuristic (SGH) that supports parallel computing is presented for solving the two-dimensional cutting stock problem with pattern reduction, where a set of rectangular items with given demand are cut from rectangular stock plates of the same size, considering both input-minimization (main objective) and pattern reduction (auxiliary objective). It is based on the sequential heuristic procedure that generates each next pattern to fulfill some portion of the remaining items and repeats until all items are fulfilled. The SGH uses a grouping technique to select the items that can be used to generate the next pattern, and adjusts the item values according to the sequential value correction method after the next pattern is generated. Each next pattern is generated using a dynamic programming recursion. The computational results indicate that the SGH is powerful in both input-minimization and pattern reduction, and the parallel computing is useful to reduce computation time.