Сибирский федеральный университет

Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций

Конференция: Springer Science and Business Media Deutschland GmbH; 14 October 2020 through 17 October 2020; 14 October 2020 through 17 October 2020

Год издания: 2020

Идентификатор DOI: 10.1007/978-3-030-63319-6_76

Ключевые слова: bin packing problem, incompatible categories, metaheuristic, priority, strip packing problem

Аннотация: 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. © 2020, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.

Журнал: Advances in Intelligent Systems and Computing

Выпуск журнала: Vol. 1295

Номера страниц: 825-836

ISSN журнала: 00253159

• Voronov Vladimir (Siberian Federal University, Krasnoyarsk, 660041, Russian Federation)
• Peresunko Pavel (Siberian Federal University, Krasnoyarsk, 660041, Russian Federation)
• Videnin Sergey (Siberian Federal University, Krasnoyarsk, 660041, Russian Federation)
• Matyukhin Nikita (Siberian Federal University, Krasnoyarsk, 660041, Russian Federation)
• Masich Igor (Siberian Federal University, Krasnoyarsk, 660041, Russian Federation)

• Scopus
• Ядро РИНЦ (eLIBRARY.RU)