Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization

Mauro Russo; Maurizio Boccia; Antonio Sforza; Claudio Sterle

doi:10.1111/itor.12687

journal article Jun 03, 2019

Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization

Mauro Russo Maurizio Boccia Antonio Sforza Claudio Sterle

International Transactions in Operational Research Vol. 27 No. 2 pp. 794-834 · Wiley

View at Publisher Save 10.1111/itor.12687

Abstract

AbstractIn the two‐dimensional (2D) cutting (2DC) problem, a large rectangular sheet has to be dissected into smaller rectangular pieces with the aim of maximizing the total profit associated with the extracted pieces. When the number of copies of each piece to be extracted is bounded, it is referred to as constrained 2DC (C2DC) problem. The C2DC has been widely studied by the operations research community for its applications and theoretical issues. In this work, we recall the best exact and heuristic solving approaches for the C2DC and we provide a review and a categorization of the available upper bounds. We also discuss improvements and combinations of these upper bounds and give directions for their effective exploitation. Finally, we demonstrate the loss of accuracy of several exact methods present in literature because of the effect of the used antiredundancy strategies on the implemented bounding criteria. This work, based on more than 90 contributions, has a twofold target. For researchers working in C2DC, it provides a useful insight on the topic. For expert practitioners, it represents a systematic collection of the main findings and achievements, posing also the basis for future research.

Topics

No keywords indexed for this article. Browse by subject →

References

97

[1]

10.1287/ijoc.1050.0169

[2]

10.1016/s0305-0548(00)00095-2

[3]

10.1007/s00291-008-0128-5

[4]

10.1111/itor.12077

[5]

10.1111/itor.12134

[6]

10.1016/j.ejor.2005.11.060

[7]

10.1057/jors.1985.51

[8]

10.1111/j.1475-3995.2009.00713.x

[9]

10.1007/s00291-011-0277-9

[10]

10.1057/jors.2011.6

[11]

10.1111/itor.12648

[12]

10.1007/s10100-018-0551-x

[13]

10.1111/j.1475-3995.2009.00701.x

[14]

10.1287/ijoc.2016.0693

[15]

10.1093/imaman/13.2.95

[16]

10.1016/s0167-6377(03)00057-9

[17]

10.1016/j.cor.2010.12.013

[18]

10.1007/s10589-007-9103-3

[19]

10.1111/itor.12390

[20]

10.1016/0377-2217(93)e0277-5

[21]

10.1287/opre.25.1.30

[22]

10.1287/ijoc.1110.0478

[23]

10.1016/j.disopt.2018.02.003

[24]

10.1287/ijoc.2018.0806

[25]

10.1016/j.mcm.2006.09.008

[26]

10.1080/0305215x.2011.600757

[27]

10.1080/0305215x.2012.658784

[28]

10.1177/0954405411421996

[29]

10.1016/j.cor.2012.03.001

[30]

10.1016/j.mcm.2011.04.003

[31]

10.1016/j.ejor.2014.06.032

[32]

10.1057/jors.2014.33

[33]

10.1057/s41274-016-0148-5

[34]

10.1111/j.1475-3995.2000.tb00194.x

[35]

10.1016/j.ejor.2011.11.002

[36]

10.1016/j.cor.2010.12.018

[37]

El Baz D. Hifi M. Saadi T. 2012.Peer‐to‐peer solution of 2D‐cutting stock problems. Proceedings of the 11th Workshop on Graphs and Combinatorial Optimization Bundeswehr University Munich Munich pp.116–120.

[38]

10.1057/palgrave.jors.2600638

[39]

10.1007/s001860400376

[40]

10.1016/j.cor.2012.07.016

[41]

10.1287/ijoc.2016.0708

[42]

10.1016/j.ejor.2011.10.018

[43]

10.1287/ijoc.2016.0710

[44]

10.1287/opre.13.1.94

[45]

10.1287/opre.14.6.1045

[46]

10.1147/rd.165.0462

[47]

10.1016/s0305-0548(96)00095-0

[48]

10.1023/b:joco.0000021938.49750.91

[49]

10.1287/opre.1040.0154

[50]

10.1007/s10589-007-9081-5

Showing 50 of 97 references

Metrics

26

Citations

97

References

Details

Published: Jun 03, 2019
Vol/Issue: 27(2)
Pages: 794-834
License: View

Authors

M

Mauro Russo

Department of Electrical Engineering and Information Technology University “Federico II” of Naples Naples 80138 Italy

M

Maurizio Boccia

Istituto di analisi dei sistemi ed informatica Antonio Ruberti Consiglio Nazionale delle Ricerche Rome 00185 Italy

A

Antonio Sforza

Department of Electrical Engineering and Information Technology University “Federico II” of Naples Naples 80138 Italy

C

Claudio Sterle

Department of Electrical Engineering and Information Technology University “Federico II” of Naples Naples 80138 Italy; Istituto di analisi dei sistemi ed informatica Antonio Ruberti Consiglio Nazionale delle Ricerche Rome 00185 Italy

Funding

Ministero dell’Istruzione, dell’Università e della Ricerca Award: PRIN 20153TXRX9

Cite This Article

Mauro Russo, Maurizio Boccia, Antonio Sforza, et al. (2019). Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization. International Transactions in Operational Research, 27(2), 794-834. https://doi.org/10.1111/itor.12687

Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization

You May Also Like