A Polynomial-Time Algorithm for Linear Cutting Stock Problem

Sang-Un, Lee

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2013, 18(7), pp.149-155
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Sang-Un, Lee ¹

¹강릉원주대학교 멀티미디어공학과

ABSTRACT

Commonly, one seeks a particular pattern suitable for stock cutting and the number of such patterns through linear programming. However, since the number of the patterns increases exponentially, it is nearly impossible to predetermine all the existing patterns beforehand. This paper thus proposes an algorithm whereby one could accurately predetermine the number of existing patterns by applying Suliman’s feasible pattern method. Additionally, this paper suggests a methodology by which one may obtain exact polynomial-time solutions for feasible patterns without applying linear programming or approximate algorithm. The suggested methodology categorizes the feasible patterns by whether the frequency of first occurrence of all the demands is distributed in 0 loss or in various losses. When applied to 2 data sets, the proposes algorithm is found to be successful in obtaining the optimal solutions.
KEYWORDS

Cutting Stock Problem, 1D-CSP, 1st Frequency, Allocation
REFERENCES (11)

[web] / Cutting Stock Problem / Wikipedia / Wikimedia Foundation Inc / http://en.wikipedia.org/wiki/Cutting_stock_problem

[journal] S. M. A. Suliman / 2001 / Pattern Generating Procedure for the Cutting Stock Problem / International Journal of Production Economics 74(1-3) : 293~301

[confproc] S. Umetani / 2001 / A Local Search Approach for One Dimensional Cutting Stock Problem / MIC 2001 - 4th Metaheuristics International Conference

[thesis] J. Nazemi / 2008 / Kiln Planning, A Cutting Stock Approach / AZAD University

[report] G. Belov / 2003 / The Number of Setups (Different Patterns) in One-Dimensional Stock Cutting / Institute for Numerical Mathematics, Dresden University

[journal] C. Goulimis / 1990 / Optimal Solutions for the Cutting Stock Problem / European Journal of Operational Research 44(2) : 197~208

[journal] P. C. Gilmore / 1961 / A Linear Programming Approach to the Cutting Stock Problem / Operations Research 9(6) : 849~859

[journal] R. W. Haessler / 1975 / Controlling Cutting Pattern Changes in One-Dimensional Trim Problems / Operations Research 23(3) : 483~493

[report] J. Bisschop / 2007 / AIMMS Optimization Modeling, AIMMS 3.8 / Paragon Decision Technology

[book] S. Umetani / 2003 / Combinatorial Optimization and Algorithms: Benchmark Problem Instances / Department. of Advanced Science and Technology, Graduate School of Engineering, Toyota Technological Institute

[journal] S. Umetani / 2003 / One Dimensional Cutting Stock Problem to Minimize the Number of Different Patterns / European Journal of Operational Research 46(2) : 388~402
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools