Algorithms for the variable sized bin packing problem

• Published in: European journal of operational research 2003-06, Vol.147 (2), p.365-372
• Main Authors: Kang, Jangha, Park, Sungsoo
• Format: Article
• Language: English
• Subjects: Algorithm; Analysis of algorithm; Combinatorial problem; Packing
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/S0377-2217(02)00247-3

In this paper, we consider the variable sized bin packing problem where the objective is to minimize the total cost of used bins when the cost of unit size of each bin does not increase as the bin size increases. Two greedy algorithms are described, and analyzed in three special cases: (a) the sizes of items and bins are divisible, respectively, (b) only the sizes of bins are divisible, and (c) the sizes of bins are not divisible. Here, we say that a list of numbers a 1, a 2,…, a m are divisible when a j exactly divides a j−1 , for each 1< j⩽ m. In the case of (a), the algorithms give optimal solutions, and in the case of (b), each algorithm gives a solution whose value is less than 11 9 C(B *)+4 11 9 , where C( B *) is the optimal value. In the case of (c), each algorithm gives a solution whose value is less than 3 2 C(B *)+1 .