An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem

Jianyu Long, Zhong Zheng (), Xiaoqiang Gao, Panos M. Pardalos and Wanzhe Hu
Additional contact information
Jianyu Long: Dongguan University of Technology
Zhong Zheng: Chongqing University
Xiaoqiang Gao: Chongqing University
Panos M. Pardalos: University of Florida
Wanzhe Hu: Chongqing University

Annals of Operations Research, 2020, vol. 289, issue 2, No 9, 311 pages

Abstract: Abstract In this study, we focus on the steel plate cutting problem (SPCP), where a set of rectangular order plates with specified demand are cut from large rectangular steel plates. The aim of solving SPCP is to minimize the number of steel plates used in the cutting process. According to the analysis of the cutting production line in steel mills, we regard the SPCP as a two-dimensional non-exact three-stage cutting stock problem (2D3SCSP) with two additional practical constraints. Since these two practical constraints limit the length between any two adjacent guillotine cuts in the first stage by a predetermined parameter and the number of guillotine cuts in the second stage by one, the existing solving methods proposed for 2D3SCSP cannot be used for SPCP directly. Four heuristics based on column generation (HCG) are proposed to solve SPCP. The performance of the four HCGs is analyzed through conducting a set of experiments, and an effective HCG with the ability of obtaining high-quality solutions within acceptable computational times is finally obtained.

Keywords: Dynamic programming; Heuristic algorithms; Mathematical programming; Optimization; Cutting stock problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-020-03604-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:289:y:2020:i:2:d:10.1007_s10479-020-03604-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-020-03604-w

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().