Online packing of arbitrary sized items into designated and multipurpose bins

Noam Goldberg and Shlomo Karhi

European Journal of Operational Research, 2019, vol. 279, issue 1, 54-67

Abstract: We consider an online multitype bin-packing problem with two item types. This setting can be motivated by transport applications in which some items may be shipped either in dry shipping containers or more costly refrigerated ones, while other items can only be transported in refrigerated containers. The problem was introduced by Goldberg and Karhi [Omega 71:85-92, 2017] who focused on the case of up to two item types, three bin types and only two item sizes. For this special case a tight (also known as optimal) absolute competitive ratio was shown of approximately 1.618. Here we consider the general problem of arbitrary item sizes and show a lower bound on the absolute competitive ratio of any online algorithm that is a function of the bin costs. This bound in the worst-case is approximately 1.781. We then extend the first-fit method to our problem setting and prove an absolute competitive ratio bound that is a function of the bin costs. In the worst case this upper bound is approximately 1.930. In addition an upper bound of 1.750 is established on the worst-case asymptotic (as the number of items grows large) competitive ratio.

Keywords: Bin packing; Type compatibility; Online algorithms; Competitive ratio analysis; Container shipping (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719304461
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:279:y:2019:i:1:p:54-67

DOI: 10.1016/j.ejor.2019.05.029

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().