본문 바로가기
  • Home

A Polynomial-Time Algorithm for Linear Cutting Stock Problem

  • 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 : Engineering > Computer Science

Sang-Un, Lee 1

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

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.