Worst-case analysis of heuristic approaches for the temporal bin packing problem with fire-ups

Research output: Contribution to journalResearch articleContributedpeer-review

Abstract

We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing a weighted sum of the total number of bins required and the number of switch-on processes (so-called fire-ups) caused during operation. So far, research on the TBPP-FU has mainly focused on exact approaches and their improvement by valid cuts or variable reduction techniques. Although these studies have revealed the problem considered here to be very difficult to cope with, theoretical contributions to heuristic solution methods have not yet been presented in the available literature. Hence, in this article we investigate the worst-case behavior of some approximation algorithms, ranging from classic online algorithms to a more sophisticated look-ahead heuristic specifically designed for the TBPP-FU. In addition, we theoretically study three heuristics the ideas of which are inspired by solution methods for generalized bin packing problems in the field of logistics. As a main contribution, we constructively show that the feasible solutions obtained by all these approaches can be arbitrarily bad. By doing so, we (i) identify a new open problem in cutting and packing, and (ii) establish another previously unknown difference between the classical TBPP and the extended problem with fire-ups, rendering the latter the more difficult problem even from a heuristic point of view.

Details

Original languageEnglish
Pages (from-to)481-499
Number of pages19
JournalAnnals of Operations Research
Volume333
Issue number1
Publication statusPublished - Feb 2024
Peer-reviewedYes

External IDs

Scopus 85163705389
ORCID /0000-0003-0953-3367/work/152544507
Mendeley 8cf832c7-9311-32d8-9c17-703bed08eed4

Keywords

Keywords

  • 90C10, 90C59, Cutting and packing, Fire ups, Heuristics, Temporal bin packing, Worst-case analysis