Online bin packing with delay and holding costs

Reference:

Lauri Ahlroth, André Schumacher, and Pekka Orponen. Online bin packing with delay and holding costs. Operations Research Letters, to appear.

Abstract:

We consider online bin packing where in addition to the emphopening cost of each bin, the arriving items collect emphdelay costs until their assigned bins are released (closed), and the open bins themselves collect emphholding costs. Besides being of practical interest, this problem generalises several previously unrelated online optimisation problems. We provide a general online algorithm for this problem with competitive ratio 7, with improvements for the special cases of zero delay or holding costs and size-proportional item delay costs.

Keywords:

competitive analysis, online algorithm, bin packing, rent-to-buy

Suggested BibTeX entry:

@article{AhSO12,
    author = {Lauri Ahlroth and André Schumacher and Pekka Orponen},
    journal = {Operations Research Letters},
    language = {eng},
    title = {Online bin packing with delay and holding costs},
    year = {to appear},
}