A Column Generation Based Heuristic for a Temporal Bin Packing Problem

Alexey Ratushnyi, Yury Kochetov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings
EditorsPanos Pardalos, Michael Khachay, Alexander Kazakov
PublisherSpringer Science and Business Media Deutschland GmbH
Pages96-110
Number of pages15
ISBN (Print)9783030778750
DOIs
Publication statusPublished - 2021
Event20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021 - Irkutsk, Russian Federation
Duration: 5 Jul 202110 Jul 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021
CountryRussian Federation
CityIrkutsk
Period05.07.202110.07.2021

Keywords

  • Bin packing
  • Column generation
  • Knapsack problem
  • Virtual machine

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES

Fingerprint

Dive into the research topics of 'A Column Generation Based Heuristic for a Temporal Bin Packing Problem'. Together they form a unique fingerprint.

Cite this