TY  - JOUR
AU  - Wongprakornkul, Sirirat 
AU  - Charnsethikul, Peerayuth 
PY  - 2010
TI  - Solving One-Dimensional Cutting Stock Problem with Discrete Demands and Capacitated Planning Objective
JF  - Journal of Mathematics and Statistics
VL  - 6
IS  - 2
DO  - 10.3844/jmssp.2010.79.83
UR  - https://thescipub.com/abstract/jmssp.2010.79.83
AB  - 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.