Packing into designated and multipurpose bins: A theoretical study and application to the cold chain

摘要

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+root 5/2 approximate to 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 3/2. 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+root 5/2 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. (C) 2016 Elsevier Ltd. All rights reserved.