Abstract
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.
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 language | English |
|---|---|
| Journal | Discrete Optimization |
| Volume | 8 |
| Issue number | 2 |
| Pages (from-to) | 333-343 |
| Number of pages | 11 |
| ISSN | 1572-5286 |
| DOIs | |
| Publication status | Published - 2011 |