Research Article Open Access

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

Sirirat Wongprakornkul and Peerayuth Charnsethikul

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.

Journal of Mathematics and Statistics
Volume 6 No. 2, 2010, 79-83

DOI: https://doi.org/10.3844/jmssp.2010.79.83

Submitted On: 25 February 2010 Published On: 30 June 2010

How to Cite: Wongprakornkul, S. & Charnsethikul, P. (2010). Solving One-Dimensional Cutting Stock Problem with Discrete Demands and Capacitated Planning Objective. Journal of Mathematics and Statistics, 6(2), 79-83. https://doi.org/10.3844/jmssp.2010.79.83

  • 3,585 Views
  • 2,406 Downloads
  • 7 Citations

Download

Keywords

  • Stochastic integer linear programming
  • cutting stock problems
  • column-generation technique
  • heuristics