An Integer Programming Approach for a 2D Bin Packing Problem with Precedence Constraints in the Sheet Metal Industry

We consider an optimization problem of practical relevance arising in Salvagnini Italia, a multinational corporation in the sheet metal industry. The problem falls into the well-know area of Two-Dimensional Bin Packing Problems, and aims at determining efficient item-to-sheet assignments by minimizing the material waste and by keeping into account several technological constraints involving, in particular, hard and soft precedence relations among groups of items. We devise two Mixed Integer Linear Programming (MILP) formulations able to address the different practical aspects of the problem. Based on the MILP models, we propose an exact approach and a matheuristic. The two methods have been applied to instances of practical relevance, and we report computational results and a comparison with the current company’s procedure.