We consider online bin packing where in addition to the \emph{opening cost} of each bin, the arriving items collect \emph{delay costs} until their assigned bins are released (closed), and the open bins themselves collect \emph{holding 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.

@article{
    AhSO13_schumach,
    author = "Ahlroth, Lauri and Schumacher, André and Orponen, Pekka",
    volume = "41",
    responsibleauthor = "Ahlroth, Lauri and Schumacher, André and Orponen, Pekka",
    doi = "10.1016/j.orl.2012.10.006",
    language = "eng",
    title = "Online bin packing with delay and holding costs",
    journal = "Operations Research Letters",
    issn = "0167-6377",
    number = "1",
    month = "January",
    note = "",
    pages = "1--6",
    juforank = "2",
    il = "no",
    year = "2013",
    keywords = "competitive analysis, online algorithm, bin packing, rent-to-buy",
    unitcode = "T306-99, T312-1",
    impactfactor = "A1",
    abstract = "We consider online bin packing where in addition to the \emph{opening cost} of each bin, the arriving items collect \emph{delay costs} until their assigned bins are released (closed), and the open bins themselves collect \emph{holding 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.",
    flags = "public HIIT copy"
}

AUTHORS:

ABSTRACT:

URL:
http://dx.doi.org/10.1016/j.orl.2012.10.006

AUTHORS:

ABSTRACT:

URL: http://dx.doi.org/10.1016/j.orl.2012.10.006

URL:
http://dx.doi.org/10.1016/j.orl.2012.10.006