New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers: model and heuristic for 1D cutting stock problem with leftovers

Yaodong Cui, Xiang Song, Yan Chen, Yi-Ping Cui

Research output: Contribution to journalArticlepeer-review

320 Downloads (Pure)

Abstract

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), items of the current order are cut from stock bars to minimize material cost. Here, stock bars include both standard ones bought commercially and old leftovers generated in processing previous orders, and cutting patterns often include new leftovers that are usable in processing subsequent orders. Leftovers of the same length are considered to be of the same type. The number of types of leftovers should be limited to simplify the cutting process and reduce the storage area. This paper presents an integer programming model for the 1DCSPUL with limited leftover types and describes a heuristic algorithm based on a column-generation procedure to solve it. Computational results show that the proposed approach is more effective than several published algorithms in reducing trim loss, especially when the number of types of leftovers is limited.
Original languageEnglish
Pages (from-to)269-280
Number of pages13
JournalJournal of the Operational Research Society
Volume68
Issue number3
Early online date7 Oct 2016
DOIs
Publication statusPublished - Mar 2017

Keywords

  • cutting and packing
  • one-dimensional cutting stock
  • column generation
  • usable leftovers

Fingerprint

Dive into the research topics of 'New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers: model and heuristic for 1D cutting stock problem with leftovers'. Together they form a unique fingerprint.

Cite this