1 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU2 Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU3 University of Haifa4 Technion5 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
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.
Discrete Optimization, 2011, Vol 8, Issue 2, p. 333-343