@article{ART001791010},
author={Sang-Un, Lee},
title={A Polynomial-Time Algorithm for Linear Cutting Stock Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2013},
volume={18},
number={7},
pages={149-155}
TY - JOUR
AU - Sang-Un, Lee
TI - A Polynomial-Time Algorithm for Linear Cutting Stock Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2013
VL - 18
IS - 7
PB - The Korean Society Of Computer And Information
SP - 149
EP - 155
SN - 1598-849X
AB - 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.
KW - Cutting Stock Problem;1D-CSP;1st Frequency;Allocation
DO -
UR -
ER -
Sang-Un, Lee. (2013). A Polynomial-Time Algorithm for Linear Cutting Stock Problem. Journal of The Korea Society of Computer and Information, 18(7), 149-155.
Sang-Un, Lee. 2013, "A Polynomial-Time Algorithm for Linear Cutting Stock Problem", Journal of The Korea Society of Computer and Information, vol.18, no.7 pp.149-155.
Sang-Un, Lee "A Polynomial-Time Algorithm for Linear Cutting Stock Problem" Journal of The Korea Society of Computer and Information 18.7 pp.149-155 (2013) : 149.
Sang-Un, Lee. A Polynomial-Time Algorithm for Linear Cutting Stock Problem. 2013; 18(7), 149-155.
Sang-Un, Lee. "A Polynomial-Time Algorithm for Linear Cutting Stock Problem" Journal of The Korea Society of Computer and Information 18, no.7 (2013) : 149-155.
Sang-Un, Lee. A Polynomial-Time Algorithm for Linear Cutting Stock Problem. Journal of The Korea Society of Computer and Information, 18(7), 149-155.
Sang-Un, Lee. A Polynomial-Time Algorithm for Linear Cutting Stock Problem. Journal of The Korea Society of Computer and Information. 2013; 18(7) 149-155.
Sang-Un, Lee. A Polynomial-Time Algorithm for Linear Cutting Stock Problem. 2013; 18(7), 149-155.
Sang-Un, Lee. "A Polynomial-Time Algorithm for Linear Cutting Stock Problem" Journal of The Korea Society of Computer and Information 18, no.7 (2013) : 149-155.
