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

Journal of Mathematics and Statistics

Sirirat Wongprakornkul¹  Peerayuth Charnsethikul¹ 

关键词: Stochastic integer linear programming;    cutting stock problems;    column-generation technique;    heuristics;   

DOI  :  10.3844/jmssp.2010.79.83

学科分类：社会科学、人文和艺术（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

Unknown