A Column Generation Based Heuristic for a Temporal Bin Packing Problem

Alexey Ratushnyi, Yury Kochetov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

We introduce a new temporal bin packing problem that originated from cloud computing. We have a finite set of items. For each item, we know an arriving time, processing time, and two weights (CPU, RAM). Some items we call large. Each bin (server) has two capacities and is divided into two identical parts (left and right). A regular item can be placed in one of them. A large item is divided into two identical parts and placed in both parts of a bin. Our goal is to pack all items into the minimum number of bins. For this NP-hard problem, we design a heuristic that is based on column generation to get lower and upper bounds. Preliminary computational experiments for real test instances indicate a small gap between the bounds. The average relative error is at most 0.88% for one week planning horizon and about 50000 items. The average running time is 21 s for a personal computer.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings
РедакторыPanos Pardalos, Michael Khachay, Alexander Kazakov
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы96-110
Число страниц15
ISBN (печатное издание)9783030778750
DOI
СостояниеОпубликовано - 2021
Событие20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021 - Irkutsk, Российская Федерация
Продолжительность: 5 июл 202110 июл 2021

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12755 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021
СтранаРоссийская Федерация
ГородIrkutsk
Период05.07.202110.07.2021

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ

Fingerprint

Подробные сведения о темах исследования «A Column Generation Based Heuristic for a Temporal Bin Packing Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать