research-article

One-dimensional stock cutting resilient against singular random defects

Authors:

Fabrizio Marinelli,

Ulrich Pferschy,

Fatemeh K. RanjbarAuthors Info & Claims

Volume 157, Issue C

https://doi.org/10.1016/j.cor.2023.106280

Published: 01 September 2023 Publication History

Abstract

When industrial components are obtained by cutting bars of raw material (stocks), production volumes and values can be affected by random defects in the stocks. To deal with this inconvenience, we propose to design reconfigurable cutting patterns that can be adjusted so that defects fall, as far as possible, in the residual area that is normally discarded. In this situation, a trade-off arises between the amount of this scrap area and the probability that there exists a reconfiguration with no loss of items. We define mathematical models for the expected economic value produced with a single stock, or with all the stocks cut to obtain the required items. We then introduce the relevant optimization problems, discuss their complexity and devise various solution algorithms, comprising dynamic programming and Integer Linear Programming. The effectiveness of our algorithms is finally illustrated by computational tests on sample problems derived from the literature.

Highlights

•

A new cutting stock problem based on a stochastic model of small defects is proposed.

•

The theoretical properties of the resulting expected utilization of stock are studied.

•

A subset sum based dynamic programming algorithm is proposed.

•

The best expected utilization of a stock with a random defect is computed.

•

ILP-based models for maximizing the total expected revenue are introduced.

References

[1]

Aboudi R., Barcia P., Determining cutting stock patterns when defects are present, Ann. Oper. Res. 82 (1998) 343–354.

[2]

Afsharian M., Niknejad A., Wäscher G., A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects, OR Spectrum 36 (4) (2014) 971–999.

[3]

Alem D.J., Morabito R., Production planning in furniture settings via robust optimization, Comput. Oper. Res. 39 (2012) 139–150.

[4]

Alem D.J., Munari P.A., Arenales M.N., Ferreira P.A.V., On the cutting stock problem under stochastic demand, Ann. Oper. Res. 179 (2010) 169–186.

[5]

Alves C., de Carvalho J.M.V., A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem, Comput. Oper. Res. 35 (4) (2008) 1315–1328.

[6]

Arbib C., Marinelli F., On cutting stock with due dates, Omega 46 (2014) 11–20.

[7]

Arbib C., Marinelli F., Maximum lateness minimization in one-dimensional bin packing, Omega 68 (2017) 76–84.

[8]

Arbib C., Marinelli F., Pezzella F., An LP-based tabu search for batch scheduling in a cutting process with finite buffers, Int. J. Prod. Econ. 2 (136) (2012) 287–296.

[9]

Arbib, C., Marinelli, F., Pınar, M.Ç., Pizzuti, A., 2022a. Assortment and Cut of Defective Stocks by Bilevel Programming. In: Proc. of the 11th Int. Conf. on Operations Research and Enterprise Systems. pp. 294–301.

[10]

Arbib C., Marinelli F., Pınar M.Ç., Pizzuti A., Robust stock assortment and cutting under defects in automotive glass production, Prod. Oper. Manage. (2022),.

[11]

Arbib C., Marinelli F., Pizzuti A., Number of bins and maximum lateness minimization in two-dimensional bin packing, European J. Oper. Res. 291 (1) (2021) 101–113.

[12]

Arbib C., Marinelli F., Ventura P., One-dimensional cutting stock with a limited number of open stacks: bounds and solutions from a new integer linear programming model, Int. Trans. Oper. Res. 1–2 (23) (2016) 47–63.

[13]

Belov G., Scheithauer G., Setup and open-stack minimization in one-dimensional stock cutting, INFORMS J. Comput. 19 (1) (2007) 27–35.

[14]

Belov G., Scheithauer G., Mukhacheva E.A., One-dimensional heuristics adapted for two-dimensional rectangular strip packing, J. Oper. Res. Soc. 59 (6) (2008) 823–832.

[15]

Beraldi P., Bruni M.E., Conforti D., The stochastic trim-loss problem, European J. Oper. Res. 197 (1) (2009) 42–49.

[16]

Carnieri C., Mendoza G.A., Luppold W.G., Optimal cutting of dimension parts from lumber with a defect: A heuristic solution procedure, Forest Prod. J. 43 (9) (1993) 66–72.

[17]

Cherri A.C., Cherri L.H., Oliveria B.B., Oliveria J.F., Carravilla M.A., A stochastic programming approach to the cutting stock problem with usable leftovers, European J. Oper. Res. 308 (1) (2023) 38–53.

[18]

Christofides N., Whitlock C., An algorithm for two-dimensional cutting problems, Oper. Res. 25 (1) (1977) 30–44.

Digital Library

[19]

Dell’Amico M., Delorme M., Iori M., Martello S., Mathematical models and decomposition methods for the multiple knapsack problem, European J. Oper. Res. 274 (3) (2019) 886–899.

[20]

Delorme M., Iori M., Martello S., Bin packing and cutting stock problems: Mathematical models and exact algorithms, European J. Oper. Res. 255 (1) (2016) 1–20.

[21]

Durak B., Tüzün D.A., Dynamic programming and mixed integer programming based algorithms for the online glass cutting problem with defects and production targets, Int. J. Prod. Res. 55 (24) (2017) 7398–7411.

[22]

Gaivoronski A.A., Lisser A., Lopez R., Xu H., Knapsack problem with probability constraints, J. Global Optim. 49 (2011) 397–413.

[23]

Garey M., Johnson D., Computers and Intractability; A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.

Digital Library

[24]

Ghodsi R., Sassani F., Real-time optimum sequencing of wood cutting process, Int. J. Prod. Res. 43 (6) (2005) 1127–1141.

[25]

Hahn S.G., On the optimal cutting of defective sheets, Oper. Res. 16 (6) (1968) 1100–1114.

[26]

Hwang J.Y., Kuo W., Ha C., Modeling of integrated circuit yield using a spatial nonhomogeneous Poisson process, IEEE Trans. Semicond. Manuf. 24 (3) (2011) 377–384.

[27]

Ide J., Tiedemann M., Westphal S., Haiduk F., An application of deterministic and robust optimization in the wood cutting industry, 4OR 13 (2015) 35–57.

[28]

Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer, 2004.

[29]

Koiliaris K., Xu C., Faster pseudopolynomial time algorithms for subset sum, ACM Trans. Algorithms 15 (3) (2019) 1–20. Article No. 40.

[30]

Krichagina E.V., Rubio R., Taksar M.I., Wein L.M., A dynamic stochastic stock-cutting problem, Oper. Res. 46 (5) (1998) 690–701.

[31]

Malaguti E., Monaci M., Paronuzzi P., Pferschy U., Integer optimization with penalized fractional values: The knapsack case, European J. Oper. Res. 273 (2019) 874–888.

[32]

Marinelli F., Pizzuti A., A sequential value correction heuristic for a bi-objective two-dimensional bin-packing, Electron. Notes Discrete Math. 64 (2018) 25–34.

[33]

Monaci M., Pferschy U., Serafini P., Exact solution of the robust knapsack problem, Comput. Oper. Res. 40 (2013) 2625–2631.

[34]

Neidlein V., Vianna A.C.G., Arenales M.N., Wäscher G., Two-dimensional guillotineable-layout cutting problems with a single defect – an AND/OR-graph approach, in: Operations Research Proceedings 2008, Part 3, Springer, 2009, pp. 85–90.

[35]

Özdamar L., The cutting-wrapping problem in the textile industry: optimal overlap of fabric lengths and defects for maximizing return based on quality, Int. J. Prod. Res. 38 (2000) 1287–1309.

[36]

Perez-Salazar S., Singh M., Toriello A., Adaptive bin packing with overflow, Math. Oper. Res. (2022),. Published online in Articles in Advance 25 Feb 2022.

Digital Library

[37]

Pernkopf M., Riegler M. Gronalt M., Profitability gain expectations for computed tomography of sawn logs, Eur. J. Wood Wood Prod. 77 (2019) 619–631.

[38]

Petutschnigg A., Pferschy U., Sattler L., Influence of production costs on cutting optimization in window frame production - a graph-theoretical model, Comput. Electron. Agric. 58 (2007) 133–143.

[39]

Petutschnigg A., Schwarzbauer P., Pferschy U., Material flow simulation to support site planning of a sawmill with an installed computer tomograph - a case study, Paper and Timber (Paperi Ja Puu) 87 (2005) 47–52.

[40]

Rönnqvist M., A methods for the cutting stock problem with different qualities, European J. Oper. Res. 83 (1995) 57–68.

[41]

Rönnqvist M., Åstrand E., Integrated defect detection and optimization for cross cutting of wooden boards, European J. Oper. Res. 108 (1998) 490–508.

[42]

Sarker B.R., An optimum solution for one-dimensional slitting problems: a dynamic programming approach, J. Oper. Res. Soc. 39 (1988) 749–755.

[43]

Schepler X., Rossi A., Gurevsky E., Dolgui A., Solving robust bin-packing problems with a branch-and-price approach, European J. Oper. Res. 297 (3) (2022) 831–843.

[44]

Scholl A., Klein R., Juergensen C., BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Comput. Oper. Res. 24 (1997) 627–645.

[45]

Sculli D., A stochastic cutting stock procedure: Cutting rolls of insulating tape, Manage. Sci. 27 (8) (1981) 946–952.

[46]

Sierra-Paradinas M., Soto-Sánchez O., Alonso-Ayuso A., Martín-Campo J., Gallego M., An exact model for a slitting problem in the steel industry, European J. Oper. Res. 295 (1) (2021) 336–347.

[47]

Wäscher G., Haußner H., An improved typology of cutting and packing problems, European J. Oper. Res. 183 (3) (2007) 1109–1130.

[48]

Wenshu L., Dan M., Jinzhuo W., Study on cutting stock optimization for decayed wood board based on genetic algorithm, Open Autom. Control Syst. J. 7 (2015) 284–289.

[49]

Woeginger G.J., Yu Z., On the equal-subset-sum problem, Inform. Process. Lett. 42 (1992) 299–302.

Index Terms

One-dimensional stock cutting resilient against singular random defects

Index terms have been assigned to the content through auto-classification.

Recommendations

Bin packing and related problems

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems-including multi-constraint variants-by simply representing all the patterns in a very compact graph. Our method ...
Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
We study pseudo-polynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudo-polynomial formulations from the literature. We ...
Strips minimization in two-dimensional cutting stock of circular items

Circular items are often produced from stock plates using the cutting and stamping process that consists of two stages. A guillotine machine divides the plate into strips at the cutting stage, and then a press punches out the items from the strips at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 157, Issue C

Sep 2023

307 pages

ISSN:0305-0548

Issue’s Table of Contents

The Authors.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 September 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents