You are here


2017/18 I. félév
Árpád tér 2. II. em. 220. sz.
Attila Bódis
Bin packing problem with scenarios

Scheduling over scenarios is one of the latest approaches in modelling scheduling problems including uncertainty. However, to the best of our knowledge, scenarios have never been used for the bin packing problem, so we have introduced the bin packing problem with scenarios. In this model, we have a list of items with sizes between 0 and 1, and each item is assigned to one or more scenarios. In reality, the items of only one scenario will occur, but this chosen scenario is unknown in the time of packing, so the algorithms have to consider every scenario. This means, that the items have to be packed into bins such, that for any scenario, the summarised size of items in this scenarios is at most 1 in each bin.
The objective function of the standard bin packing problem is to minimize the number of bins. We introduce some extensions of this objective functions to the scenario based model, and we show our competitive analysis of some bin packing algorithms, like NextFit, FirstFit, AnyFit and Harmonic, adapted for scenarios.

Everyone is welcome.