Hybrid heuristic for the one-dimensional cutting stock problem with usable leftovers and additional operating constraints

被引:0
作者
Bertolinia, Massimo [1 ]
Mezzogoria, Davide [1 ]
Zammorib, Francesco [2 ]
机构
[1] Univ Modena & Reggio Emilia, Modena, Italy
[2] Univ Parma, Parma, Italy
关键词
Cutting Stock Problem; Simulated Annealing; Multiple Stock Lengths; Production Scheduling; Metal Bars; LINEAR-PROGRAMMING APPROACH; GROUPING GENETIC ALGORITHM; BIN PACKING PROBLEM; COLUMN-GENERATION; LOCAL SEARCH; OPTIMIZATION;
D O I
10.5267/j.ijiec.2023.10.006
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
The One-Dimensional Cutting Stock Problem consists in cutting long bars into smaller ones, to satisfy customers' demand, minimizing waste and cost. In this paper the standard problem is extended with the inclusion of additional constraints that are generally neglected in scientific literature, although relevant in many industrial applications. We also modified the standard objective function, by assuming that bars may have a different economical value and a different processing or shipping priority. Moreover, in line with business requirements, among solutions that generate the same cutting waste, we prefer the ones that generate a low number of leftovers, especially if leftovers are long, so that the likelihood of their reuse is high. To solve the problem, we propose a Simulated Annealing based heuristic, which exploits a specific neighbor search. The heuristic is implemented in a parametric way that allows the user to set the priorities of the bars and to choose the specific sub-set of constraints he or she wants to consider. The heuristic is finally tested on many problem instances, and it is compared to three benchmarks and to one commercial software. The outcomes of this comparative analysis demonstrate both its quality and effectiveness.(c) 2024 by the authors; licensee Growing Science, Canada
引用
收藏
页码:149 / 170
页数:22
相关论文
共 42 条
  • [1] Abuhassan I.A., 2011, INT J RES REV APPL S, V6
  • [2] A hybrid improvement heuristic for the one-dimensional bin packing problem
    Alvim, ACF
    Ribeiro, CC
    Glover, F
    [J]. JOURNAL OF HEURISTICS, 2004, 10 (02) : 205 - 229
  • [3] [Anonymous], 2010, Journal of Research and Reviews in Applied Sciences
  • [4] Balogh J., 2014, PROC 26 ANN ACM SIAM, P1425
  • [5] Three-step solutions for cutting stock problem of construction steel bars
    Benjaoran, Vacharapoom
    Bhokha, Sdhabhon
    [J]. KSCE JOURNAL OF CIVIL ENGINEERING, 2014, 18 (05) : 1239 - 1247
  • [6] Project Time Deployment: a new lean tool for losses analysis in Engineer-to-Order production environments
    Bertolini, Massimo
    Braglia, Marcello
    Marrazzini, Leonardo
    Neroni, Mattia
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2022, 60 (10) : 3129 - 3146
  • [7] Comparison of new metaheuristics, for the solution of an integrated jobs-maintenance scheduling problem
    Bertolini, Massimo
    Mezzogori, Davide
    Zammori, Francesco
    [J]. EXPERT SYSTEMS WITH APPLICATIONS, 2019, 122 : 118 - 136
  • [8] Better-Fit Heuristic for One-Dimensional Bin-Packing Problem
    Bhatia, A. K.
    Hazra, M.
    Basu, S. K.
    [J]. 2009 IEEE INTERNATIONAL ADVANCE COMPUTING CONFERENCE, VOLS 1-3, 2009, : 193 - +
  • [9] THE CUTTING STOCK PROBLEM - A SURVEY
    CHENG, CH
    FEIRING, BR
    CHENG, TCE
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1994, 36 (03) : 291 - 305
  • [10] The one-dimensional cutting stock problem with usable leftover - A heuristic approach
    Cherri, Adriana Cristina
    Arenales, Marcos Nereu
    Yanasse, Horacio Hideki
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 196 (03) : 897 - 908