 Packing into designated and multipurpose bins: A theoretical study and application to the cold chainNoam Goldberg and Shlomo Karhi Omega, 2017, vol. 71, issue C, 85-92 Abstract: We consider a multitype bin packing problem and focus on the particular case of an online setting with two types of items and three bin types: two designated bins and a multipurpose bin that can store both types of items. The flexibility of multipurpose bins comes at a greater cost per bin and the objective is to minimize the cost of bins used. First, we establish a competitive ratio lower bound for the unit size problem as a function of the bin cost parameters; over all bin costs the resulting worst-case competitive ratio is 1+52≈1.618. Next, we show that the first-fit algorithm׳s competitive ratio is tight (it equals the established lower bound) for the two-size standard bin packing problem (in the absence of item and bin types) with an absolute competitive ratio of 32. Then, we generalize our analysis for the problem with two item types, where each item type has a distinct size; the worst-case absolute competitive ratio is shown to be 1+52 as in the unit size case. Finally, we apply our results to analyze mixed load packing of perishable items given current spot prices of dry and refrigerated shipping containers. Date: 2017 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:71:y:2017:i:c:p:85-92 Ordering information: This journal article can be ordered from DOI: 10.1016/j.omega.2016.09.010 Access Statistics for this article Omega is currently edited by B. Lev More articles in Omega from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.