Semi-Online Bin Stretching with Bunch Techniques

Michaël Gabay (1) , Vladimir Kotov (2) , Nadia Brauner (3)

1 G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 Department of Applied Mathematics and Computer Science [Minsk]
3 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production

We are given a sequence of items that can be packed into $m$ unit size bins and the goal is to assign these items online to $m$ bins while minimizing the stretching factor. Bins have infinite capacities and the stretching factor is the size of the largest bin. We present an algorithm with stretching factor 26/17 improving the best known algorithm by Kellerer and Kotov with a stretching factor 11/7. Our algorithms has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose.

Mots clés: Bin stretching; Multiprocessor scheduling; Online algorithms; Bin packing

Domaines: Recherche opérationnelle [math.OC]

Michaël Gabay, Vladimir Kotov, Nadia Brauner. Semi-Online Bin Stretching with Bunch Techniques. 2013. ⟨hal-00869858v1⟩