A Two-Dimensional Multi-criteria Bin Packing Problem in the Production of Printed Circuit Boards

The classical two-dimensional bin packing problem is to put small rectangular items into larger rectangular bins without overlapping, so that the items are completely inside a bin and a minimum number of bins are used. In this paper, the items have a given demand, i.e. the bins must contain a certain number of copies of each item type. In addition, the number of patterns should also be minimised. A pattern is an arrangement of items within a bin. The primary optimisation goals are to minimise the number of bins used and the different patterns. To achieve these goals and to better utilise the area of the bins, additional optional items can be used. However, the use of optional items is associated with costs. We also need to consider distance constraints which depend on the items and are influenced by whether guillotine cuts are used or not. The problem was motivated by the company Precoplat/MicroCirtec GmbH based in Krefeld, Germany, in an effort to reduce changeover times and waste in multi-layer printed circuit board production.