Страница публикации

Fast Heuristic Algorithms for the Multiple Strip Packing Problem

Авторы: Vasilyev I., Ushakov A.V., Barkova M.V., Zhang D., Ren J., Chen J.

Журнал: Communications in Computer and Information Science: 20th Intern. Conf. on Mathematical Optimization Theory and Operations Research (MOTOR 2021, Virtual, Online, 5 - 10 July 2021)

Том: 1476

Номер:

Год: 2021

Отчётный год: 2021

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI: 10.1007/978-3-030-86433-0_20

Аннотация: In this paper we address the so-called two-dimensional Multiple Strip Packing Problem (MSPP). There is a set of rectangles and a set of strips, where each strip has a pre-defined width. The problem is to find a feasible packing of all the rectangles into the strips so as the maximal height of the packing over all the strips is minimized. A packing is feasible if all the rectangles are placed into the strips and not overlapped. In case of only one strip, the problem is widely known as the Strip Packing Problem (SPP). Many effective constructive heuristics for SPP are based on the so-called skyline representation of a packing pattern. We generalized this approach for the case of multiple strips and developed a randomized local search, which embeds the proposed skyline heuristic to compute the objective value for a packing. We also introduced the two-dimensional level multiple strip packing problem and developed some level-based constructive heuristics. We report computational results on real-life problem instances arisen in an application of MSPP in scheduling computing jobs on multiple Spark computer clusters.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0