A NEW HEURISTIC ALGORITHM FOR THE ONE-DIMENSIONAL CUTTING STOCK PROBLEM

BERBERLER M. E., NURİYEV U.

APPLIED AND COMPUTATIONAL MATHEMATICS, cilt.9, sa.1, ss.19-30, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 9 Sayı: 1
  • Basım Tarihi: 2010
  • Dergi Adı: APPLIED AND COMPUTATIONAL MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.19-30
  • Anahtar Kelimeler: Cutting Stock Problem, Bin. Packing Problem, Subset-Sum Problem, Dynamic Programming, Heuristic Algorithm, LINEAR-PROGRAMMING APPROACH, PACKING
  • Dokuz Eylül Üniversitesi Adresli: Hayır

Özet

This paper describes an attempt to solve the one-dimensional cutting stock problem heuristically by using dynamic programming used to solve subset-sum problem which is considered as a sub-problem. Thisway an optimal solution is found for the sub-problem, which yields solution for the original problem. Thus an economical gain is achieved by decreasing the rate of trim loss. Moreover the cutting-cost can be reduced by minimizing the number of different cutting-patterns by this algorithm. Toward this goal, a new mathematical model is proposed and a novel algorithm is developed. The proposed algorithm is coded with Delphi and then through computational experiments on real-life constrainted optimization problems, the results are compared with the others in the literature. The computational experiments show the efficiency of the algorithm.