A Two-Dimensional 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 that produces computer numerical control (CNC) machines designed to cut and bend the sheet metal. We focus on cutting machines and we face the problem of determining efficient cutting layouts, that is, given a set of rectangular items to be cut, we want to place them in the available material sheets with the objective of minimizing the waste. This problem falls into the well-known area of Two-Dimensional Bin Packing Problems (2DBPP) and, given its possible application in multiple fields, several variants have been proposed during the last decades in the Operations Research literature. Nevertheless, the problem under study presents a set of attributes that, to the best of our knowledge, has never been considered yet. More precisely, we take into account the following practical aspects, coming from the specific cutting technology: two items can either share a side (common cut) or need to be placed at a given minimum distance, and the same may be imposed between an item and the sheets border; 90 degrees rotation is allowed and each item may have mandatory or forbidden placement areas; a hard (resp. soft) precedence may be assigned to each item, meaning that a production order has to be determined for material sheets and items with higher precedence need to (resp. should, the waste being the same) be produced before the others; optional items are also considered. We devise a Mixed Integer Linear Programming (MILP) model able to inte- grate the different attributes. Moreover, in order to pursue a secondary objective of proposing an as compact as possible cutting layout, we present a post-process optimization based on a Strip Packing MILP formulation. The proposed models have been solved on preliminary instances of practical relevance by means of Cplex. Results indicates that the packing model well integrates the new practical features and that, in combination with the post- process optimization, it returns solutions that fully match the companys needs. [1] M. DellAmico, J. C. Diaz, M. Iori, The Bin Packing Problem with