Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: 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 usiПоказать полностьюng 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