Algorithms for the variable sized bin packaging problem

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...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2003-06, Vol.147 (2), p.365
Main Authors: Kang, Jangha, Park, Sungsoo
Format: Article
Language:English
Subjects:
Algorithms
Mathematical models
Optimization
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 a1,a2,...,am are divisible when aj exactly divides aj-1, for each 1. 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 , where C(B*) is the optimal value. In the case of (c), each algorithm gives a solution whose value is less than .
ISSN:0377-2217
1872-6860