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.
DOI: https://doi.org/10.3844/jmssp.2010.79.83
Copyright: © 2010 Sirirat Wongprakornkul and Peerayuth Charnsethikul. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 4,462 Views
- 2,868 Downloads
- 7 Citations
Download
Keywords
- Stochastic integer linear programming
- cutting stock problems
- column-generation technique
- heuristics