One-dimensional stock cutting resilient against singular random defects

• Published in: Computers & operations research 2023-09, Vol.157, p.106280, Article 106280
• Main Authors: Arbib, Claudio, Marinelli, Fabrizio, Pferschy, Ulrich, Ranjbar, Fatemeh K.
• Format: Article
• Language: English
• Subjects: Bin packing; Cutting stock; Dynamic programming; Mixed integer programming; Recoverable defects
• ISSN: 0305-0548
• DOI: 10.1016/j.cor.2023.106280

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. •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.