?
New Metaheuristic for Priority Guillotine Bin Packing Problem with Incompatible Categories and Sequential Deformation
The paper considers the formulation of a new priority packing problem with incompatible categories and dynamically changing bin sizes, which is a variant of the well-known bin packing problem. This is a challenging optimization problem that is often encountered in the context of cutting ingots of non-ferrous and precious metals using a guillotine. We use the concepts of priority and incompatibility of categories combined with the need to split the base bin into components to reflect the specifics of the problem being solved. Incompatibility of categories follows from the grouping of rectangles by thickness, and priorities determine the desired order of production. A problem with independent categories can be represented as a multiple strips packing problem. In our case, however, the bin lengths are limited to the minimum and maximum values and are not known in advance. In this regard, it becomes necessary not only to find the optimal cutting scheme, but also the optimal bin lengths. We propose a sequential metaheuristics (SM) to solve this problem. It is based on splitting a set of rectangles into groups. They are formed according to the priorities and weights of the rectangles. Individual groups are sequentially placed in their own bins. Then bins with rectangles of the same category are combined. The basis is a simple deterministic single-pass priority heuristic (PH). It uses its own priorities to select the most appropriate rectangles for packing. The results presented are based on extensive computational experiments performed on the generated benchmark datasets. The tested instances differ in number of items, categories, priorities and bin capacities. Computational experiments show that the SM algorithm can effectively solve the problem.
In book
