An efficient approach for large-scale two-dimensional guillotine cutting stock problems

Abstract

We present an efficient method for solving approximately both constrained and unconstrained two-dimensional cutting stock problems. The algorithm guarantees a constant approximation ratio for some versions of the problem. The performance of the proposed algorithm is evaluated on several large-scale randomly generated problem instances and on many instances of the literature. Computational results show that our algorithm produces high-quality solutions within reasonable computational times.

Keywords:

• combinatorial optimisation
• cutting problem
• dynamic programming
• heuristics
• knapsack problem