Online Variable-Sized Bin Packing with Conflicts

Leah Epstein, Lene Monrad Favrholdt, Asaf Levin

Research output: Contribution to journalJournal articleResearchpeer-review


We study a new kind of on-line bin packing with conflicts,
motivated by a problem arising when scheduling jobs on the Grid.
In this bin packing problem, the set of items is given at the
beginning, together with a set of conflicts on pairs of items. A
conflict on a pair of items implies that they cannot be assigned
to a common bin. The online scenario is realized as follows.
Variable-sized bins arrive one by one, and items need to be
assigned to each bin before the next bin arrives. We analyze the
online problem as well as semi-online versions of it, which are
the variant where the sizes of the arriving bins are
monotonically non-increasing as well as the variant where they are
monotonically non-decreasing.
Original languageEnglish
JournalDiscrete Optimization
Issue number2
Pages (from-to)333-343
Number of pages11
Publication statusPublished - 2011

Cite this