Solving One-Dimensional Cutting Stock Problem with Discrete Demands and Capacitated Planning Objective

Abstract

Problem statement: One-dimensional cutting stock problem with discrete demands and capacitated planning objective is an NP hard problem. Approach: The mathematical model with column-generation technique by a branch-and-bound procedure and the heuristic based on the first fit decreasing method are proposed. Then, both approaches were compared and some characteristics were investigated such as upper-bound value, percentage above lower-bound value, computation time, and number of patterns. Results: The 24 instances were examined. The proposed heuristic provides the upper-bound value above the lower-bound around 0-16.78%. All upper-bound values from column-generation and integer programming are better than the proposed heuristic but all computation times are higher. Conclusion: The proposed heuristic has consistently high performance in computation times.