Heuristic for the two-dimensional arbitrary stock-size cutting stock problem

• Published in: Computers & industrial engineering 2014-12, Vol.78, p.195-204
• Main Authors: Cui, Yaodong, Cui, Yi-Ping, Yang, Liu
• Format: Article
• Language: English
• Subjects: Algorithms; Arbitrary stock-size cutting stock; Comparative analysis; Cost engineering; Cutting; Cutting stock problem; Decision analysis; Heuristic; Plates; Purchasing; Purchasing decision; Raw materials; Studies; Two dimensional; Two-dimensional cutting
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2014.10.009

•A heuristic for the 2D arbitrary stock-size cutting stock problem is presented.•A procedure with all-capacity property is proposed to obtain the patterns.•The algorithm outperforms a published heuristic in solution quality.•Trim loss can be reduced significantly by using the algorithm. A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier’s provisions, such that the plate cost is minimized. The supplier’s provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.