Solving the Two-Dimensional Knapsack Problem Considering Cutting-Time and Emission of Particulate Matter in the Metalworking Industry

Abstract

Abstract— This article presents a metaheuristic to solve the two-dimensional knapsack problem on applications of metalworking industries. The proposed algorithm is based on a GRASP procedure and its performance is assessed through comparison of the solutions computed for the knapsack problem. We have used two references for comparison: instances reported in the literature and experimental data obtained with two variations on the cutting method. The first reference allows us to conclude about the used area and the computational time. The second reference let us to explore the performance of the solutions with respect to the cutting-time and the amount of particles emitted. The methodology is composed by four steps: (1) selection of the instances, (2) design and implementation of the algorithms for optimization and post-optimization, (3) computing of the solutions and registering of cutting-times and particles emitted for each solution and (4) performance validation through comparison of solutions. The results permit to conclude a good behavior of the proposed algorithm reaching the performance reported in some instances and improving others. Additionally, the algorithm exhibits a stable computational time even for large-scale instances. It is emphasized that the post-optimization stage reduces the cutting-times without incrementing the emission of particulate matter. As future work we propose: to include a vision system to close the cutting loop; to consider partial damages on the plate; and to contemplate an exact approach for the sequencing cutting problem.